Question: I want to proof by induction:

$ \sum\_{k=m}^{n} {n \choose k}{k \choose m} = {n \choose m}2^{n-m}$

given that $n,m \in \mathbb{N}$ and $0 \leq m \leq n$

I have done that the proof for the first element $m=n$:

$ {n \choose m} = {n \choose m}$

but now when doing:
$ \sum\_{k=m}^{n+1} {n+1 \choose k}{k \choose m} = {n+1 \choose m}2^{(n+1)-m}$

I got stuck here:
$\sum\_{k=m}^{n+1} {n+1 \choose k}{k \choose m} = \sum\_{k=m}^{n} {n+1 \choose k}{k \choose m} + {n+1 \choose k}{k \choose m}$

because of the usage of n+1 inside the sum... What am I missing here?

thanks!

Answer: 
if your goal is to evaluate $\lim\_{n\rightarrow\infty}\sqrt[n]{\sum\_{k=0}^{n}x^{k}}$ so a standard squeeze theorem trick gives for $x\geq1$

> 
> $x=\sqrt[n]{x^{n}}\le\sqrt[n]{\sum\_{k=0}^{n}x^{k}}\le\sqrt[n]{(n+1)\cdot x^{n}}=\sqrt[n]{n+1}\cdot x$
> 
> 
> 

and therefore the desired limit equals to $x$. and for $0\le x<1$,

> 
> $1=\sqrt[n]{1}\le\sqrt[n]{\sum\_{k=0}^{n}x^{k}}\le\sqrt[n]{n+1}{}{\longrightarrow}1$
> 
> 
> 

so the limit is $1$ in that case
This is certainly the case for $|x|<1,$ for then the radicand becomes at $n=+\infty,$ the quantity $$\frac{1}{1-x},$$ so that the root of the quantity expressed as $$(1-x)^{-1/n}=e^{{-1/n}\log(1-x)}$$ goes to $1$ at infinity. This fails for $x=1,$ since then the quantity becomes $(1+n)^{1/n},$ which goes to $e$ at infinity. On the other hand, at $x=-1,$ we have that the quantity becomes, when $n$ is odd, $0,$ and when $n$ is even, $1,$ so that the limit fails to exist in this case. Finally when $x>1,$ the radicand being comparable to $x^{n+1},$ has an $n$th root which goes to something different from $1.$