# Jay's question at Yahoo! Answers regarding a proof by mathematical induction

#### MarkFL

Staff member
Here is the question:

Need help with math induction?

For all natural numbers n, the sum 1+4+4^(2) +4^(3) +. . .+4^(n) = (1/3) * (4^(n+1)−1).

Any help would be appreciated. Thanks!
I have posted a link there to this thread so the OP can see my work.

#### MarkFL

Staff member
Hello Jay,

We are given to prove by induction:

$$\displaystyle \sum_{j=0}^n\left(4^j \right)=\frac{4^{n+1}-1}{3}$$

First, let's verify the base case $P_1$ is true:

$$\displaystyle \sum_{j=0}^1\left(4^j \right)=\frac{4^{1+1}-1}{3}$$

$$\displaystyle 4^0+4^1=\frac{4^2-1}{3}$$

$$\displaystyle 1+4=\frac{15}{3}$$

$$\displaystyle 5=5$$

The base case is true, so let's state the induction hypothesis $P_k$:

$$\displaystyle \sum_{j=0}^k\left(4^j \right)=\frac{4^{k+1}-1}{3}$$

As our inductive step, lets add $$\displaystyle 4^{k+1}$$ to both sides:

$$\displaystyle \sum_{j=0}^k\left(4^j \right)+4^{k+1}=\frac{4^{k+1}-1}{3}+4^{k+1}$$

$$\displaystyle \sum_{j=0}^{k+1}\left(4^j \right)=\frac{4^{k+1}-1+3\cdot4^{k+1}}{3}$$

$$\displaystyle \sum_{j=0}^{k+1}\left(4^j \right)=\frac{4\cdot4^{k+1}-1}{3}$$

$$\displaystyle \sum_{j=0}^{k+1}\left(4^j \right)=\frac{4^{(k+1)+1}-1}{3}$$

We have derived $P_{k+1}$ from $P_k$, thereby completing the proof by induction.