Welcome to our community

Be a part of something great, join today!

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

  • Thread starter
  • Admin
  • #1

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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.
 
  • Thread starter
  • Admin
  • #2

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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.