Show that $2^n-(n-1)2^{n-2}+\frac{(n-2)(n-3)}{2!}2^{n-4}-...=n+1$

Question

If n is a positive integer I need to show that

$2^n-(n-1)2^{n-2}+\frac{(n-2)(n-3)}{2!}2^{n-4}-...=n+1$

My guess: Somehow I need two equivalent binomial expression whose coefficients I need to compare.But which two binomial expressions? I know not!

P.S:Don't use Sterling Numbers or very high level maths...

Answer 1

I leave the judgement of uniqueness to the reader.

Let use consider the $r+1$th term of $$(2x^a-x^b)^{m-r}$$ which will be

$$\binom{m-r}r2^{m-2r}(-1)^rx^{am+r(b-2a)}$$

WLOG choose $b=2,a=1$

So, $\displaystyle\binom{m-r}r2^{m-2r}(-1)^r$ will be the coefficient of $x^m$ of in $\displaystyle(2x-x^2)^{m-r}$

$$\implies\sum_{r=0}^{2r\le m}\binom{m-r}r2^{m-2r}(-1)^r$$ will be the coefficient of $x^m$ in the expansion of $$\sum_{r=0}^{2r\le m}(2x-x^2)^{m-r}$$

i.e., in the expansion of $$\sum_{r=0}^m(2x-x^2)^{m-r}=\sum_{u=0}^m(2x-x^2)^u=\dfrac{1-(2x-x^2)^{m+1}}{1-(2x-x^2)}=\{1-(2x-x^2)^{m+1}\}(1-x)^{-2}$$

i.e., in the expansion of $\displaystyle(1-x)^{-2}$

Now the coefficient in $x^n(n\ge0)$ in $\displaystyle(1-x)^{-2}$ (assuming the convergence) is

$$\dfrac{(-1)^n(-2)(-3)\cdots(-n)(-n-1)}{n!}=n+1$$

Answer 2

You can prove it by induction on $n$. Let

$$f(n)=\sum_{k\ge 0}(-1)^k2^{n-2k}\binom{n-k}k\;.$$

Then for the induction step you have

$$\begin{align*} f(n+1)&=\sum_{k\ge 0}(-1)^k2^{n+1-2k}\binom{n+1-k}k\\ &=2\sum_{k\ge 0}(-1)^k2^{n-2k}\left(\binom{n-k}k+\binom{n-k}{k-1}\right)\\ &=2f(n)-2\sum_{k\ge 0}(-1)^k2^{n-2-2k}\binom{n-1-k}k\\ &=2f(n)-\sum_{k\ge 0}(-1)^k2^{n-1-2k}\binom{n-1-k}k\\ &=2f(n)-f(n-1)\\ &=2(n+1)-n\\ &=n+2\;. \end{align*}$$

Answer 3

We can develop the Linear Recurrence $$ \begin{align} a_n &=\sum_{k=0}^n(-1)^k\binom{n-k}{k}2^{n-2k}\\ &=\sum_{k=0}^n(-1)^k\left[\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\right]2^{n-2k}\\ &=2\sum_{k=0}^{n-1}(-1)^k\binom{n-k-1}{k}2^{n-2k-1}-\sum_{k=0}^{n-2}(-1)^k\binom{n-k-2}{k}2^{n-2k-2}\\[6pt] &=2a_{n-1}-a_{n-2} \end{align} $$ which has the characteristic equation $$ x^2-2x+1=0 $$ which has a double root at $x=1$. Thus, the solution has the form $$ a_n=c_0\cdot1^n+c_1n\cdot1^n $$ Since $a_0=1$ and $a_1=2$, we get $$ a_n=n+1 $$

Answer 4

Here is a generating function approach $$ \begin{align} \sum_{n=0}^\infty a_nx^n &=\sum_{n=0}^\infty\sum_{k=0}^n(-1)^k\binom{n-k}{k}2^{n-2k}x^n\tag{1}\\ &=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^k\binom{n-k}{k}2^{n-2k}x^n\tag{2}\\ &=\sum_{k=0}^\infty\left(-\frac14\right)^k\sum_{n=k}^\infty\binom{n-k}{k}(2x)^n\tag{3}\\ &=\sum_{k=0}^\infty\left(-\frac14\right)^k\sum_{n=0}^\infty\binom{n}{k}(2x)^{n+k}\tag{4}\\ &=\sum_{k=0}^\infty\left(-\frac x2\right)^k\sum_{n=0}^\infty\binom{n}{k}(2x)^n\tag{5}\\ &=\sum_{k=0}^\infty\left(-\frac x2\right)^k\sum_{n=0}^\infty(-1)^{n-k}\binom{-k-1}{n-k}(2x)^n\tag{6}\\ &=\sum_{k=0}^\infty\left(-\frac x2\right)^k\sum_{n=0}^\infty(-1)^n\binom{-k-1}{n}(2x)^{n+k}\tag{7}\\ &=\sum_{k=0}^\infty\left(-x^2\right)^k\sum_{n=0}^\infty(-1)^n\binom{-k-1}{n}(2x)^n\tag{8}\\ &=\sum_{k=0}^\infty\left(-x^2\right)^k\frac1{(1-2x)^{k+1}}\tag{9}\\ &=\frac1{1-2x}\frac1{1+\frac{x^2}{1-2x}}\tag{10}\\ &=\frac1{(1-x)^2}\tag{11}\\ &=\sum_{k=0}^\infty(-1)^k\binom{-2}{k}x^k\tag{12}\\ &=\sum_{k=0}^\infty(k+1)x^k\tag{13}\\ \end{align} $$ Explanation:
$\phantom{0}(2)$: change order of summation
$\phantom{0}(3)$: move $(-1)^k2^{-2k}=\left(-\frac14\right)^k$ out front
$\phantom{0}(4)$: substitute $n\mapsto n+k$
$\phantom{0}(5)$: move $(2x)^k$ out front
$\phantom{0}(6)$: $\binom{n}{k}=\binom{n}{n-k}=(-1)^{n-k}\binom{-k-1}{n-k}$ (see this answer)
$\phantom{0}(7)$: substitute $n\mapsto n+k$
$\phantom{0}(8)$: move $(2x)^k$ out front
$\phantom{0}(9)$: Binomial Theorem
$(10)$: sum of a geometric series
$(11)$: simplification
$(12)$: Binomial Theorem
$(13)$: $(-1)^k\binom{-2}{k}=\binom{k+1}{k}=\binom{k+1}{1}=k+1$

Equating the coefficients of $x^k$, we get $a_n=n+1$.