# Math Help - Induction Proof

1. ## Induction Proof

Been having a few problems understanding the logic (step by step process) of Induction. If someone could help me out on the following, it would be greatly appreciated!

Prove using induction:

1 + 3 + 5 + ... + (2n-1) = (n+1)^2

Thanks.

2. To understand the logic of induction, I will just quote Wikipedia:

"It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one."

So let's do this with your problem:

Our conjecture (called $P_{n}$) is $1+3+5+...+(2n-1)=n^2$

1)First, let's check if the first term (when n = 1) is true:

$P_{1}$ is $2(1)-1 = 1^2$

$1=1\therefore P_{1}$ is true.

2)Now, by letting n = k, we consider our conjecture for $P_{k}$:

$1+3+5+...+(2k-1)=\color{blue}k^2$

3)Then, by letting n = (k + 1), we consider the next case ( $P_{k+1}$)

$\color{blue}1+3+5+...+(2k-1)\color{black}+(2[k+1]-1) = (k+1)^2$

Notice how the blue part is actually $P_{k}$. Thus, we may replace that series by the summation formula (all blue expressions are equal to each other):

$\color{blue}k^2\color{black}+2k+1=(k+1)^2$

$k^2+2k+1=k^2+2k+1$

$\therefore P_{k+1}$ is true

4)So, $P_{k}$ being true necessarily implies that $P_{k+1}$ must also be true. Knowing that $P_{1}$ is true, we may use this (by letting k = 1), to conclude that $P_{2}$ is also true, and then (by replacing k = 2) conclude that $P_{3}$ is also true, repating this processes ad infinitum.

$\therefore P_{n}$ is true and the conjecture is proven.

3. Wow, Referos, thank you. I've been struggling with inductive proofs for weeks and the way you illustrated the concept, something clicked this time.

Thanks!