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

Question

This is Exercise 1.9.3 of F. M. Goodman's "Algebra: Abstract and Concrete".

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

My Attempt:

I tried induction on $n$ as follows.

Base: Try when $n=1$. Then $LHS=3^1=3$ and $$\begin{align} RHS&=\sum_{k=0}^1{(-1)^k\binom{1}{k}4^{1-k}} \\ &=(-1)^0\binom{1}{0}4^1+(-1)^1\binom{1}{1}4^0 \\ &=4-1 \\ &=3 \end{align}$$ so the result holds for $n=1$.

Assume the result for $n=r\in\mathbb{N}$. Then $$3^r=\sum_{k=0}^r{(-1)^k\binom{r}{k}4^{r-k}}.$$

Consider when $n=r+1$: I have $3^{r+1}=3\cdot 3^r=3\sum_{k=0}^r{(-1)^k\binom{r}{k}4^{r-k}}$ and have considered $$\sum_{k=0}^{r+1}{(-1)^k\binom{r+1}{k}4^{r+1-k}}$$ by writing $\binom{r+1}{k}=\binom{r}{k}+\binom{r}{k-1}$ but to no avail.

Answer 1

Start with

$$ \sum_{k=0}^{r+1} (-1)^k\binom{r+1}{k}4^{r+1-k} = 4^{r+1} + \sum_{k=1}^{r+1} (-1)^k\Bigg( \binom{r}{k} + \binom{r}{k-1}\Bigg)4^{r+1-k}$$

$$ = 4^{r+1} + \sum_{k=1}^{r+1} (-1)^k\binom{r}{k}4^{r+1-k} + \sum_{k=1}^{r+1} (-1)^k\binom{r}{k-1}4^{r+1-k}.$$

In the first sum the term $k=r+1$ is zero and you can add in the $k=0$ term back. In the second sum, reindex your $k$ to go from $0$ to $r$. So you'll have

$$ \sum_{k=0}^{r+1} (-1)^k\binom{r+1}{k}4^{r+1-k} = \sum_{k=0}^{r} (-1)^k\binom{r}{k}4^{r+1-k} + \sum_{k=0}^{r} (-1)^{k+1}\binom{r}{k}4^{r-k}. $$

Using your induction hypothesis,

$$ = 4*3^{r} - 3^{r} = 3^{r+1}.$$

However a much quicker proof would be to use the binomial theorem:

$$ (x+y)^r = \sum_{k=0}^{r} \binom{r}{k} x^k y^{r-k} $$

with $x=-1$ and $y=4$.

Answer 2

Hint: if you multiply by $4^{-n}$ and use the binomial theorem, you should get $$ \left(1 - \frac{1}{4}\right)^n $$

Answer 3

One option is to notice the right side is a binomial expansion. But your solution should work. For the induction step, we have

$$\begin{align*} & \sum_{k=0}^{r+1}(-1)^k\binom{r+1}{k}4^{r+1-k} \\ =& 4^{r+1}+\sum_{k=1}^{r+1} (-1)^k\binom{r+1}{k}4^{r+1-k} \\ =& 4^{r+1}+\sum_{k=0}^r (-1)^{k+1}\binom{r+1}{k+1} 4^{r-k} \\ =& 4^{r+1}+\sum_{k=0}^{r-1} (-1)^{k+1}\left( \binom{r}{k+1}+\binom{r}{k}\right)4^{r-k} + (-1)^{r-1}\\ =& 4^{r+1}+\sum_{k=0}^{r-1}(-1)^{k+1}\binom{r}{k+1}4^{r-k}+\sum_{k=0}^{r-1}(-1)^{k+1}\binom{r}{k}4^{r-k}+(-1)^{r-1} \\ =& 4^{r+1}+\sum_{k=1}^{r}(-1)^k\binom{r}{k}4^{r-k+1}-\sum_{k=0}^{r}(-1)^k\binom{r}{k}4^{r-k}+(-1)^{r}+(-1)^{r-1} \\ =& 4^{r+1}+\sum_{k=0}^{r}(-1)^k\binom{r}{k}4^{r-k+1}-4^{r+1}-3^r \\ =& 4\sum_{k=0}^{r}(-1)^k\binom{r}{k}4^{r-k}-3^r \\ =& 4 \cdot 3^r - 3^r \\ =& 3\cdot 3^r \\ =& 3^{r+1} \end{align*}$$

Answer 4

$$\begin{align} \sum_{k=0}^n(-1)^k\binom nk 4^{n-k} &=4^n\sum_{k=0}^n \binom nk \left(-\frac14\right)^k\\ &=4^n\left(1-\frac 14\right)^n\\ &=4^n\left(\frac 34\right)^n\\ &=3^n\end{align}$$