Find 2 sums with the binomial newton
Find the sum of:
i)$\displaystyle\sum_{k=0}^{n} k^2$ $\left(\begin{array}{c} n\\k\end{array}\right)$
ii) $\displaystyle\sum_{k=1}^{n} \frac{2k+5}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$
Thoughts:
i)(After the Edit)$\displaystyle\sum_{k=0}^{n} k^2$ $\left(\begin{array}{c} n\\k\end{array}\right)$ = $\displaystyle\sum_{k=0}^{n} {k(k-1)}$ $\left(\begin{array}{c} n\\k\end{array}\right)$ + $\displaystyle\sum_{k=0}^{n}{k}$ $\left(\begin{array}{c} n\\k\end{array}\right)$= $\displaystyle\sum_{k=0}^{n} {n(k-1)}$ $\left(\begin{array}{c} n-1\\k-1\end{array}\right)$ + $\displaystyle\sum_{k=0}^{n}{n}$ $\left(\begin{array}{c} n-1\\k-1\end{array}\right)$= $\displaystyle\sum_{k=0}^{n} {n(n-1)}$ $\left(\begin{array}{c} n-2\\k-2\end{array}\right)$ + n$\displaystyle\sum_{k=0}^{n}$ $\left(\begin{array}{c} n-1\\k-1\end{array}\right)$= $n(n-1)2^{n-2}+n2^{n-1}$=$n2^{n-2}(2+n-1)$=$n(n+1)2^{n-2}$
ii)(After the Edit)$\displaystyle\sum_{k=1}^{n} \frac{2k+5}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$= $\displaystyle\sum_{k=1}^{n} \frac{(2k+2)+3}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$= 2$\displaystyle\sum_{k=1}^{n}$$\left(\begin{array}{c} n\\k\end{array}\right)$ + 3$\displaystyle\sum_{k=1}^{n} \frac{1}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$=
$2^{n+1}-2$+ $\frac{3}{n+1}$$\displaystyle\sum_{k=1}^{n} \frac{n+1}{k+1}$$\left(\begin{array}{c} n\\k\end{array}\right)$= $2^{n+1}-2$+ $\frac{3}{n+1}$$\displaystyle\sum_{k=1}^{n}$$\left(\begin{array}{c} n+1\\k+1\end{array}\right)$= $2^{n+1}-2+\frac{3}{n+1}(2^{n+1}-1)$
$\endgroup$ 42 Answers
$\begingroup$Hint:
ii) We can expand as follows \begin{align*} \sum_{k=1}^n\frac{2k+5}{k+1}{n\choose k}&=\sum_{k=1}^n\frac{(2k+2)+3}{k+1}{n\choose k}\\[4pt] &=\sum_{k=1}^n 2{n\choose k}+\frac{3}{n+1}\sum_{k=1}^n\frac{n+1}{k+1}{n\choose k}\\[4pt] &=2\sum_{k=1}^n{n\choose k}+\frac{3}{n+1}\sum_{k=1}^n{{n+1}\choose {k+1}} \end{align*}
Notice $$\sum_{k=0}^n{n\choose k}=2^n\qquad\implies\qquad\sum_{k=1}^n{n\choose k}=2^n-1,$$ then, \begin{align*} \sum_{k=1}^n\frac{2k+5}{k+1}{n\choose k}&=2\sum_{k=1}^n{n\choose k}+\frac{3}{n+1}\sum_{k=1}^n{{n+1}\choose {k+1}}=2(2^n-1)+\frac{3}{n+1}(2^{n+1}-1) \end{align*} Which can be reduced as $$\sum_{k=1}^n\frac{2k+5}{k+1}{n\choose k}=\frac{2^{n+1}(n+4)-2n-5}{n+1}$$
$\endgroup$ 3 $\begingroup$For the first one:
We know that:
$$ \sum_{k=0}^{n}{{n\choose k}x^k}={(1+x)}^{n} $$
So let's differentiate it to get:
$$ \sum_{k=0}^{n}{k{n\choose k}{x}^{k-1}}=n{(1+x)}^{n-1} $$
Multiply by $x$ and differntiate again:
$$ \sum_{k=0}^{n}{k^2{n\choose k}{x}^{k-1}}=(nx{(1+x)}^{n-1})'\\ \sum_{k=0}^{n}{k^2{n\choose k}{x}^{k-1}}=n({(1+x)}^{n-1}+(n-1)x{(1+x)}^{n-2})\\ $$
Multiply by $x$ one more time to get:
$$ \sum_{k=0}^{n}{k^2{n\choose k}{x}^{k}}=nx({(1+x)}^{n-1}+(n-1)x{(1+x)}^{n-2})\\ $$ Now just put $x=1$ and you'll get the answer.
Let's move on to the next one:
$$ \sum_{k=0}^{n}{\frac{2k+5}{k+1}{n\choose k}x^k} =2\sum_{k=0}^{n}{\frac{k}{k+1}{n\choose k}x^k}+5\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}\\ =2\sum_{k=0}^{n}{(1-\frac{1}{k+1}){n\choose k}x^k}+5\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}\\ =2\sum_{k=0}^{n}{{n\choose k}x^k}-2\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}+5\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}\\ =2{(1+x)}^{n}-2\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}+5\sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k} $$
Now let's compute :
$$ \sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k} $$
We have:
$$ \sum_{k=0}^{n}{{n\choose k}x^k} = {(1+x)}^{n} $$
Let's integrate to get:
$$ \sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}{x}^{k+1}}=\frac{{(1+x)}^{n+1}}{n+1}+C $$
For $x=0$ the sum is $0$ so :
$$ C=-\frac{1}{n+1} $$
We finally get:
$$ \sum_{k=0}^{n}{\frac{1}{k+1}{n\choose k}x^k}=\frac{1}{x}(\frac{{(1+x)}^{n+1}}{n+1}-\frac{1}{n+1}) $$
$$ \sum_{k=0}^{n}{\frac{2k+5}{k+1}{n\choose k}x^k} = 2{(1+x)}^{n}-2(\frac{1}{x}(\frac{{(1+x)}^{n+1}}{n+1}-\frac{1}{n+1}))+5(\frac{1}{x}(\frac{{(1+x)}^{n+1}}{n+1}-\frac{1}{n+1})) $$ Now plug in $x=1$ and you'll get the answer
$\endgroup$
