Induction Proof that $\sum_{i=0}^n 3^{n-i} {n \choose i} = \sum_{i=0}^n (-1)^i 5^{n-i} {n \choose i}$

Question

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc (-1)^n\binom{n}{n}$$

I believe this needs to be proved by induction but I'm not sure how to do it.

Help is appreciated!

Answer 1

We have

$$(x+a)^n=\sum_{k=0}^{n}\binom{n}{k}x^ka^{n-k}$$

Now by putting $x=3$ and $a=1$ we get $$\begin{align}(3+1)^n&=\sum_{k=0}^{n}\binom{n}{k}(3)^k(1)^{n-k}\\ &=\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n}\\ \end{align}$$

And by putting $x=5$ and $a=-1$ we get $$\begin{align}(5+(-1))^n&=\sum_{k=0}^{n}\binom{n}{k}(5)^k(-1)^{n-k}\\ &=\binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc (-1)^n\binom{n}{n}\\ \end{align}$$

Since $$(3+1)^n=(5+(-1))^n=(5-1)^n=4^n$$ we get

$$4^n=\sum_{k=0}^{n}\binom{n}{k}3^k1^{n-k}=\sum_{k=0}^{n}\binom{n}{k}5^k(-1)^{n-k}$$