Discrete Mathematics - Combinatorics proof

$$\\$$ I need to prove $$\displaystyle\sum\limits_{k=0}^n\left(\frac{ 1^k+(-1)^k}{2}\right)\cdot\left(\begin{array}{c}n\\ k\end{array}\right)4^k=\frac{5^n+(-3)^n}{2}$$ my Attempt below

$$\displaystyle\sum\limits_{k=0}^n\left(\frac{ 1^k+(-1)^k}{2}\right)\cdot \left(\begin{array}{c}n\\ k\end{array}\right)4^k=\frac{1^0+(-1)^0}{2}\cdot \frac{n!}{0!(n-0)!}\cdot4^0\\ +\frac{1^1+(-1)^1}{2}\cdot \frac{n!}{1!(n-1)!}\cdot4^1+\frac{1^2+(-1)^2}{2}\cdot \frac{n!}{2!(n-2)!}\cdot4^2+\frac{1^3+(-1)^3}{2}\cdot \frac{n!}{3!(n-3)!}\cdot4^3+...+\frac{1^n+(-1)^n}{2}\cdot \frac{n!}{n!(n-n)!}\cdot4^n=\\ =\frac{1+1}{2}\cdot \frac{n!}{1n!}\cdot1+\frac{1+1}{2}\cdot \frac{n!}{2(n-2)!}\cdot16+\dotso+\frac{1^n+(-1)^n}{2}\cdot \frac{n!}{n!(n-n)!}\cdot4^n=\\= \frac{n!}{n!}+ \frac{4n!}{(n-1)!}+1\cdot \frac{16n!}{2(n-2)!} +1\frac{64n!}{6(n-3)!}+1\dotsm\ \frac{4^nn!}{n!(n-n)!}+1=$$

$$\frac{1}{2}\left[\sum_{k = 0}^{n} \binom{n}{k}4^k + \sum_{k = 0}^{n} \binom{n}{k}(-4)^k\right]=\\$$1/2$$(1+x)^n=\frac{1}{2}((1+4)^n+(1-4)^n=\frac{5^n+(-3)^n}{2}$$

• What keeps this from looking like the form of a summation in the Binomial Theorem? Can you force the equation into that form? – Matthew Daly Aug 20 at 9:55

Observe that $$\sum_{k = 0}^{n} \left(\frac{1^k + (-1)^k}{2}\right)\binom{n}{k}4^k = \frac{1}{2}\left[\sum_{k = 0}^{n} \binom{n}{k}4^k + \sum_{k = 0}^{n} \binom{n}{k}(-4)^k\right]$$ By the Binomial Theorem, $$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k}x^k$$ For the first summation, $$x = 4$$; for the second summation $$x = -4$$.
$$\sum\limits_{k=0}^n 1^{k} 4^{k}\binom {n} {k}$$ is the expansion of $$(1+4)^{n}$$ and $$\sum\limits_{k=0}^n (-1)^{k} 4^{k}\binom {n} {k}$$ is the expansion of $$(1-4)^{n}$$.
By the binomial of Newton it's just $$\frac{1}{2}((1+4)^n+(1-4)^n).$$