Show $\sum_{k=0}^{n}2^{n-k}\binom{a+k}{k}\frac{a-k}{a+k}=\binom{a+n}{n}$

Question

How it can be shown that:

$$\sum_{k=0}^{n}2^{n-k}\binom{a+k}{k}\frac{a-k}{a+k}=\binom{a+n}{n}$$

Where $a \ne 0$

---

My try:

$$\sum_{k=0}^{n}2^{n-k}\binom{a+k}{k}\frac{a-k}{a+k}=\sum_{k=0}^{n}2^{n-k}\binom{a+k}{a}\frac{a-k}{a+k}$$

$$=\frac{1}{a}\sum_{k=0}^{n}2^{n-k}\binom{a+k-1}{a-1}\left(a-k \right)$$ $$=\sum_{k=0}^{n}2^{n-k}\binom{a+k-1}{a-1}-\frac{1}{a}\color{red}{\sum_{k=0}^{n}2^{n-k}\binom{a+k-1}{a-1}k }$$

On the other hand:

$$\color{red}{\sum_{k=0}^{n}2^{n-k}\binom{a+k-1}{a-1}k}=\sum_{k=0}^{n}\left(a+k-1\right)2^{n-k}\binom{a+k-2}{k-1} $$

But computing these expressions takes much time and I think there should be a better way, but I cannot find that way.

Please if it's possible, then do the proof using elementary ways.

Answer 1

I know you would prefer a combinatorial proof and thinks that induction does not tell us anything, but since you would like to know an algebraic proof, I'll just include an inductive proof for completion's sake.

Base case $n = 0$: $$ \sum_{k=0}^0 2^{-k}{a + k \choose k}\frac{a - k}{a + k} = 2^0 {a \choose 0}\frac{a}{a} = 1 = {a \choose 0} $$ Assume true for $n = m$. For $n = m+1$: \begin{align*} \sum_{k=0}^{m+1} 2^{m+1-k}{a + k \choose k}\frac{a - k}{a + k} &= 2\sum_{k=0}^m, 2^{m-k}{a + k \choose k}\frac{a - k}{a + k} + {a + m + 1 \choose m + 1}\frac{a - m - 1}{a + m + 1} \\ &= 2{a + m \choose m} + {a + m + 1 \choose m + 1}\left(\frac{a - m - 1}{a + m + 1}\right) \\ &= 2\left(\frac{m + 1}{a + m + 1}\right){a + m + 1 \choose m + 1} + \left(\frac{a - m - 1}{a + m + 1}\right) {a + m + 1 \choose m + 1} \\ &= \left(\frac{a - m - 1 + 2(m + 1)}{a + m + 1}\right) {a + m + 1 \choose m + 1} \\ &= {a + m + 1 \choose m + 1} \end{align*} This completes the induction.

Answer 2

Here is an algebric proof :

Let $ a $ be a real, let's define the function $ f_{a} $ as follows : $$ \left(\forall x\in\left]-\frac{1}{2},\frac{1}{2}\right[\right),\ f_{a}\left(x\right)=\displaystyle\frac{1-2x}{\left(1-x\right)^{a+1}} $$

know : \begin{aligned} \left(\forall x\in\left]-\frac{1}{2},\frac{1}{2}\right[\right),\ f_{a}\left(x\right)&=\displaystyle\frac{2}{\left(1-x\right)^{a}}-\displaystyle\frac{1}{\left(1-x\right)^{a+1}}\\ &=2\displaystyle\sum_{n=0}^{+\infty}{\left(-1\right)^{n}\displaystyle\binom{-a}{n}x^{n}}-\displaystyle\sum_{n=0}^{+\infty}{\left(-1\right)^{n}\displaystyle\binom{-a-1}{n}x^{n}} \end{aligned} Observe that forall $ \left(x,n\right)\in\mathbb{R}\times\mathbb{N} $ : $ \ \ \ \ \ \ \ \ \ \ \left(-1\right)^{n}\binom{-x}{n}=\frac{\left(-1\right)^{n}}{n!}\prod\limits_{k=0}^{n-1}{\left(-x-k\right)}=\frac{1}{n!}\prod\limits_{k=0}^{n-1}{\left(x+k\right)}=\frac{1}{n!}\prod\limits_{k=0}^{n-1}{\left(x+n-1-k\right)}=\binom{x+n-1}{n} $

Thus, \begin{aligned}\left(\forall x\in\left]-\frac{1}{2},\frac{1}{2}\right[\right),\ f_{a}\left(x\right)=\displaystyle\sum_{n=0}^{+\infty}{\left(2\displaystyle\binom{a+n-1}{n}+\displaystyle\binom{a+n}{n}\right)x^{n}}\end{aligned}

Since $ \binom{a+n-1}{n}=\frac{a}{a+n}\binom{a+n}{n} $, we get, \begin{aligned}\left(\forall x\in\left]-\frac{1}{2},\frac{1}{2}\right[\right),\ f_{a}\left(x\right)=\displaystyle\sum_{n=0}^{+\infty}{\displaystyle\frac{a-n}{a+n}\displaystyle\binom{a+n}{n}x^{n}}\end{aligned}

Observe $ \left(\forall x\in\left]-\frac{1}{2},\frac{1}{2}\right[\right),\ \frac{f_{a}\left(x\right)}{1-2x}=\frac{1}{\left(1-x\right)^{a+1}} $, meaning that forall $ x \in\left]-\frac{1}{2},\frac{1}{2}\right[ $, \begin{aligned} \left(\displaystyle\sum_{n=0}^{+\infty}{\displaystyle\frac{a-n}{a+n}\displaystyle\binom{a+n}{n}x^{n}}\right)\left(\displaystyle\sum_{n=0}^{+\infty}{2^{n}x^{n}}\right)&=\displaystyle\sum_{n=0}^{+\infty}{\left(-1\right)^{n}\displaystyle\binom{-a-1}{n}x^{n}} \\ \iff \displaystyle\sum_{n=0}^{+\infty}{\left(\displaystyle\sum_{k=0}^{n}{2^{n-k}\displaystyle\binom{a+k}{k}\displaystyle\frac{a-k}{a+k}}\right)x^{n}}&=\displaystyle\sum_{n=0}^{+\infty}{\displaystyle\binom{a+n}{n}x^{n}}\end{aligned} Which leads to the following : $$ \left(\forall n\in\mathbb{N}\right),\ \displaystyle\sum_{k=0}^{n}{2^{n-k}\displaystyle\binom{a+k}{k}\displaystyle\frac{a-k}{a+k}}=\displaystyle\binom{a+n}{n} $$