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:

\(\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, let's 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.