<s>[INST] 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}$ 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! 
 [/INST] 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}$$

</s>