So a proof by induction follows a particular pattern (there are slightly different flavors out there, but they amount to the same thing). You have a statement, say P(n) that you want to prove by induction holds for all n. You begin by showing P(1) is true. Then you assume P(k) is true for some k, and show that P(k) => P(k+1)

This is the most elementary kind of induction proof. they can get more complicated in that you have to proof for numbers higher than 1. I've done induction proofs where i had to prove up to P(6) before the proof could work. anyway, here they are

Let P(n) be “1 + 3 + 5 + ... + (2n – 1) = n^2” for all positive integer nExercise 3:

This implies P(1): 2(1) – 1 = 1 = 1^2. So P(1) is true

Assume P(k) true for some k > 1, we show P(k+1)

Since P(k) holds, 1 + 3 1 + 3 + 5 + ... + (2k – 1) = k^2

=> P(k+1): 1 + 3 1 + 3 + 5 + ... + (2k – 1) + (2(k+1) – 1)

.................= P(k) + (2(k+1) – 1)

.................= k^2 + (2k + 1)

.................= (k+1)(k+1)

.................= (k+1)^2

Thus we see, P(k+1) holds.

Therefore, we conclude P(n) holds for all n

Let P(n) be “1+5+9+...+(4n-3)=2n^2-n” for every positive integer nExercise 4:

This implies P(1): 4(1) – 3 = 1 = 2(1)^2 – 1. So P(1) is true.

Assume P(k) is true for some k > 1, we show P(k+1)

Since P(k) holds, 1+5+9+...+(4k-3) = 2k^2 – k

=> P(k+1) : 1 + 5 + 9 + ... + (4k – 3) + (4(k+1) – 3)

.................= P(k) + (4(k+1) – 3)

.................= 2k^2 – k + 4(k+1) – 3

.................= 2k^2 + 4k + 4 – k – 3

.................= 2k^2 + 4k + 2 – k – 1

.................= 2(k^2 + 2k + 1) – (k + 1)

.................= 2(k+1)^2 – (k+1)

Thus we see, P(k+1) holds.

Therefore, we conclude P(n) holds for all n.