Suma de combinari

[turcas]

Calculati

\( \sum_{k=0}^{n} 2^k \cdot C_{2n-k}^n \)

[Tudor Micu]

\( C_{2n-k}^{n} \) este coeficientul lui \( x^n \) in \( (1+x)^{2n-k} \), deci termenul general al sumei, \( 2^{k}\cdot C_{2n-k}^{n} \), este coeficientul lui \( x^n \) din \( 2^k\cdot (1+x)^{2n-k}=2^{2n}\frac{(1+x)^{2n-k}}{2^{2n-k}}=2^{2n}(\frac{1+x}{2})^{2n-k} \)
Rezulta ca \( \sum_{k=0}^{n}2^k\cdot C_{2n-k}^{n} \) este coeficientul lui \( x^n \) din \( S_{1}=2^{2n}\sum_{k=0}^{n}(\frac{1+x}{2})^{2n-k}=2^{2n}\sum_{k=n}^{2n}(\frac{1+x}{2})^k \)
Fie \( S_{2}=2^{2n}\sum_{k=0}^{n-1}(\frac{1+x}{2})^k \). Observam ca \( S_{2} \) nu contine termeni \( x^n \), deci suma din problema este coeficientul lui \( x^n \) din \( S=S_{1}+S_{2}=2^{2n}\sum_{k=0}^{2n}(\frac{1+x}{2})^k \)
\( S=2^{2n}\frac{(\frac{1+x}{2})^{2n+1}-1}{\frac{1+x}{2}-1}=\frac{2^{2n+1}-(1+x)^{2n+1}}{1-x} \)
Avem formula \( 1+x+x^2+x^3+\ldots+x^m=\frac{x^{m+1}-1}{x-1} \)
x a fost arbitrar ales la inceputul problemei. Putem sa il luam subunitar si pe m putem sa il facem sa tinda la infinit. Astfel, ajungem la formula:
\( \frac{1}{1-x}=1+x+x^2+x^3+\ldots+x^{n-1}+x^{n}+x^{n+1}+\ldots \)
Avem deci \( S=(2^{2n+1}-(1+x)^{2n+1})(1+x+x^2+x^3+
\ldots+x^{n-1}+x^n+\ldots) \), de aici avem ca suma cautata (coeficientul lui \( x_n \) in S) este \( 2^{2n+1}-T \), unde \( T=(1+C_{2n+1}^1+C_{2n+1}^2+\ldots+C_{2n+1}^n) \)
Dar \( C_{2n+1}^k=C_{2n+1}^{2n+1-k} \) si deci \( T=\frac{1}{2}\sum_{k=0}^{2n+1}C_{2n+1}^K=\frac{1}{2}\cdot 2^{2n+1}=2^{2n} \)
Avem deci ca suma cautata este \( 2^{2n+1}-2^{2n}=2^{2n} \)