Mathematical Induction

Question

How to prove this with mathematical induction?

Answer 1

Inductive proofs follow this general recipe:

1. You first show it to be true for some n (usually n=1).
2. Then you assume it is true for n = m. This is the hypothesis, and it is often used in the proof.
3. Then you must show that assuming it to be tru for n = m, leads to it being true for n = m+1

For the posted problem....

n = 1: summation is 1, right hand side is 1(4-1)/3 = 3/3 = 1 so it is true for n=1

Assume

n

∑ (2k-1)² = m(4m² - 1) /3 is true for n=m. This is the hypothesis.

k

Now let n=m+1:

m+1 m

∑ (2k-1)² = ∑ (2k-1)² + (2(m+1)-1)²

k=1 k=1

where the RHS has been broken into two terms such that we can apply the hypothesis to the first term on the RHS:

m+1

∑ (2k-1)² = m(4m²-1) /3 + (2(m+1)-1)²

k=1

The RHS expands to (4m³+12m²+11m+3)/3

Now, one way to go is to check if this is the same as m+1 plugged into n(4n²-1)/3

(m+1)(4(m+1)² - 1)/3 =

(m+1)(4m²+8m+3)/3 =

( 4m³+8m²+3m+4m²+8m+3 )/3 =

(4m³+12m²+11m+3)/3

So, yes, the two expressions are the same and the proof is complete.

Another way to go is to factor (4m³+12m²+11m+3)/3:

(4m³+12m²+11m+3)/3 =

(m+1)(2m+1)(2m+3) / 3 =

(m+1)(4m²+8m+3) / 3 =

Noting that the 2nd factor is 4(m+1)²-1:

(m+1)(4(m+1)²- 1) / 3 (done, recall n=m+1 so you can replace "m+1" with "n" and end up with the hypothesis expression).