Sums of series
Task number: 3871
Sum up the following series by using the generating functions:
Variant
\(\displaystyle \sum_{k=0}^n \binom{n}{k}^2\)
Hint
Use convolution of two sequences.
Solution
Let’s denote
\(\displaystyle c_n=\sum_{k=0}^n \binom{n}{k}^2,\ a_k= \binom{n}{k},\ b_{n-k}=\binom{n}{k}=\binom{n}{n-k}\) i.e. \(b_k=a_k\), a \(\displaystyle c_n=\sum_{k=0}^n a_kb_{n-k}\),
We realize thet the generating funtion of the sequence \((a_n)_{n=0}^\infty\) is \(\displaystyle a(x)=b(x)=\sum_{k=0}^n\binom{n}{k}x^k=(1+x)^n\),
and thus \(\displaystyle c(x)=a(x)b(x)=(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k\).
The desired sum si the coefficient by \(x^n\).
Answer
The sum of the series is \(\binom{2n}n\).
Variant
\(\displaystyle \sum_{k=0}^n (-1)^k{n \choose k}^2\)
Answer
The sum is the coefficient by \(x^n\) in the polynomial \((1-x)^n(1+x)^n\), that is \(\binom{n}{n/2} (-1)^{n/2}\) for even \(n\), otherwise \(0\).
Variant
\(\displaystyle \sum_{k=0}^n k\cdot 2^k\)
Hint
Method 1: Derive function for the sum of series \(1+x+x^2+…+x^n\).
Method 2 (more general): Use the formula for the generating function of the partial sums of a sequence.
Solution
Method 1:
Let’s denote: \(\displaystyle f(x)=\sum_{k=0}^n x^k = \frac{1-x^{n+1}}{1-x} \),
by the derivation we get:
\(\displaystyle f'(x)=\sum_{k=0}^n k x^{k-1} = \frac{-(n+1)x^n(1-x)-(-1)(1-x^{n+1})}{(1-x)^2}= \frac{nx^{n+1}-(n+1)x^n+1}{(1-x)^2} \).
If we now subtitute \(x=2\), we get
\(\displaystyle \sum_{k=0}^n k 2^k = 2 \sum_{k=0}^n k 2^{k-1} = 2 f'(2) = 2\cdot\frac{n2^{n+1}-(n+1)2^n+1}{(1-2)^2}= (n-1) 2^{n+1}+2 \).
Method 2: Let’s denote \(a_k=k\cdot 2^k\) a \(\displaystyle s_n=\sum_{k=0}^n k\cdot 2^k=\sum_{k=0}^n a_k\),
then the generating functions \(\displaystyle s(x)=\sum_{n=0}^\infty s_nx^n\) and \(\displaystyle a(x)=\sum_{n=0}^\infty a_nx^n\)
are related as \(\displaystyle s(x)=\frac{a(x)}{1-x}\), protože \((s_n)_{n=0}^\infty\) is the sequence of partial sums of the sequence \((a_n)_{n=0}^\infty\).
The generating function of the sequence \((a_n)_{n=0}^\infty\) is obtained from the generating function of the arithmetic sequence \((1{,}2,3,…)\) by shifting to the right and substituting \(2x\), i.e.
\(\displaystyle a(x)=\frac{2x}{(1-2x)^2}\) and \(\displaystyle s(x)=\frac{2x}{(1-2x)^2(1-x)}\).
To now express \(s(x)\) as a series, we need to decompose the fraction into partial fractions and express each of these fractions as a series by using the generalized binomial theorem.
\(\displaystyle s(x)=\frac{2x}{(1-2x)^2(1-x)}= \frac{2}{1-x}+\frac{2}{(1-2x)^2}-\frac{4}{1-2x}= 2\sum_{n=0}^\infty x^n + 2 \sum_{n=0}^\infty \binom{n+1}{1}(2x)^n - 4 \sum_{n=0}^\infty (2x)^n = \sum_{n=0}^\infty (2 + 2 (n+1) 2^n - 4 {\cdot} 2^n) x^n = \sum_{n=0}^\infty ((n-1) 2^{n+1}+2) x^n \)
Answer
The sum of the series is \((n-1) 2^{n+1}+2\).
Variant
\(\displaystyle \sum_{k=0}^n k {n \choose k}\)
Hint
Extract \(n\) from the binomial coefficient.
Answer
\(n2^{n-1}\),
Variant
\(\displaystyle \sum_{k=0}^n k^2 \binom{n}{k}\)
Hint
Extract \(n(n-1)\) from the binomial coefficient and use the previous variant.
Answer
\(n(n+1)2^{n-2}\)
