W.22. Sa se demonstreze ca \( \sum_{k=0}^{n}\frac{(-1)^{k}}{C_{n}^{k}}=\frac{(n+1)(1+(-1)^{n}}{n+2} \), unde \( C_{n}^{k}=\frac{n!}{k!(n-k)!} \).
Jozseph Wildt International Contest, 2005
Identitate combinatoriala clasica
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Cezar Lupu
- Site Admin
- Posts: 612
- Joined: Wed Sep 26, 2007 2:04 pm
- Location: Bucuresti sau Constanta
- Contact:
Identitate combinatoriala clasica
Last edited by Cezar Lupu on Thu Mar 06, 2008 1:45 pm, edited 1 time in total.
An infinite number of mathematicians walk into a bar. The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. The bartender says “You’re all idiots”, and pours two beers.
-
lasamasatelas
- Euclid
- Posts: 27
- Joined: Fri Nov 16, 2007 10:44 am
- Contact:
Fie \( S \) suma cautata. Avem \( n!S=\sum_{k=0}^n(-1)^kk!(n-k)! \), care este coeficientul lui \( x^n \) in \( fg \), unde \( f,g \) sunt seriile formale \( f=\sum_{n\geq0}(-1)^nn!x^n \) si \( g=\sum_{n\geq0}n!x^n \).
(In general, daca \( f={\sum}a_nx^n,g={\sum}b_nx^n \), atunci \( fg={\sum}c_nx^n \), unde \( c_n=\sum_{k=0}^na_kb_{n-k} \).)
Notam \( F=xf=\sum_{n\geq0}(-1)^nn!x^{n+1} \) si \( G=xg=\sum_{n\geq0}n!x^{n+1} \). Atunci \( n!S \) e coeficientul lui \( x^{n+2} \) in \( x^2fg=FG \).
Se verifica usor ca \( F=x(1-xF\prime) \) si \( G=x(1+xG\prime) \). Prin inmultire obtinem \( F(1+xG\prime)=G(1-xF\prime) \), care implica \( x(FG\prime+GF\prime)=G-F=x(g-f) \), deci \( (FG)\prime=g-f=\sum_{n\geq0}(1-(-1)^n)n!x^n \). Rezulta ca \( FG=\sum_{n\geq0}(1-(-1)^n)\frac{n!}{n+1}x^{n+1}+C \). Constanta \( C=0 \) pt. ca \( FG \) nu are termen liber.
Identificand coeficientul lui \( x^{n+2} \) in \( FG \) obtinem \( n!S=(1-(-1)^{n+1})\frac{(n+1)!}{n+2} \) deci \( S=(1+(-1)^n)\frac{n+1}{n+2} \) c.c.t.d..
(In general, daca \( f={\sum}a_nx^n,g={\sum}b_nx^n \), atunci \( fg={\sum}c_nx^n \), unde \( c_n=\sum_{k=0}^na_kb_{n-k} \).)
Notam \( F=xf=\sum_{n\geq0}(-1)^nn!x^{n+1} \) si \( G=xg=\sum_{n\geq0}n!x^{n+1} \). Atunci \( n!S \) e coeficientul lui \( x^{n+2} \) in \( x^2fg=FG \).
Se verifica usor ca \( F=x(1-xF\prime) \) si \( G=x(1+xG\prime) \). Prin inmultire obtinem \( F(1+xG\prime)=G(1-xF\prime) \), care implica \( x(FG\prime+GF\prime)=G-F=x(g-f) \), deci \( (FG)\prime=g-f=\sum_{n\geq0}(1-(-1)^n)n!x^n \). Rezulta ca \( FG=\sum_{n\geq0}(1-(-1)^n)\frac{n!}{n+1}x^{n+1}+C \). Constanta \( C=0 \) pt. ca \( FG \) nu are termen liber.
Identificand coeficientul lui \( x^{n+2} \) in \( FG \) obtinem \( n!S=(1-(-1)^{n+1})\frac{(n+1)!}{n+2} \) deci \( S=(1+(-1)^n)\frac{n+1}{n+2} \) c.c.t.d..