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

[MarkFL]

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]

Hello Jay,

We are given to prove by induction:

$$\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:

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

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

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

$$5=5$$

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

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

As our inductive step, let's add $$4^{k+1}$$ to both sides:

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

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

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

$$\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.