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 $\displaystyle P_{n}$) is $\displaystyle 1+3+5+...+(2n-1)=n^2$

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

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

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

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

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

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

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

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

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

$\displaystyle k^2+2k+1=k^2+2k+1$

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

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

$\displaystyle \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!