# mathematical induction?

S(n) = 1^2 + 2^2 + ... +n^2 = [n(n+1)(2n+1)]/6

How do i prove that this is true for all positive integers n using mathematical induction?

Relevance

Let say

S(n) = 1^2 + 2^2 + ... +n^2 = [n(n+1)(2n+1)]/6

is true for n

for n+1

LHS

S(n+1)

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

= [n(n+1)(2n+1)]/6 + (n+1)^2

= (2n^3 + 3n^2 + n)/6 + 6(n^2 + 2n + 1)/6

= (2n^3 + 9n^2 + 13n + 6)/6

= (n+1)(n+2)(2n+3)/6

= [(n+1)((n+1)+1)(2(n+1)+1)]/6

RHS

true for n +1

when n=1,

S(1) = 1^2 = 1 (LHS)

S(1) = (1)(1+1)(2x1 + 1)/6 = 1 (RHS)

So ,use induction mathematic

S(n) = 1^2 + 2^2 + ... +n^2 = [n(n+1)(2n+1)]/6

is true for all positive integers n

Source(s): myseah
• Anonymous

You need two things: a base case and an "inductive leap of faith". Then you prove both.

In this particular instance, your base case will be S(1), and your "leap of faith" will be that if it is true for S(n), then it is also true for S(n+1).

S(1) = 1^2 = 1 * 2 * 3 / 6 = 1.

Sp. true for S(n), prove for S(n + 1).

Goal: prove that S(n+1) = (n + 1)(n + 2)(2n + 3) / 6

= (n^2 + 3n + 2)(2n + 3) / 6

= (2n^3 + 9n^2 + 13n + 6) / 6

S(n+1) = S(n) + (n+1)^2 = S(n) + n^2 + 2n + 1

And then substitute the equation for S(n), using the inductive hypothesis:

S(n+1) = n(n + 1)(2n + 1) / 6 + n^2 + 2n + 1

= (2n^3 + 3n^2 + n) / 6 + n^2 + 2n + 1

= ((2n^3 + 3n^2 + n) + (6n^2 + 12n + 6)) / 6

= (2n^3 + 9n^2 + 13n + 6) / 6

By the way, you should make sure you understand this proof, and then try to apply it to something else.

• Proof: By Mathematical Induction.

P(1): 1^2 = 1 = 1 = 6/6 = 1*2*3/6 = 1(1+1)(2*1+1)/6.

P(n+1): Assume Inductive Hypothesis: 1^2+2^2+3^2+...+n^2 = n(n+1)(2n+1)/6. We need to prove 1^2+2^2+3^2+...+(n+1)^2 = (n+1)(n+2)(2n+3)/6.

LHS: 1^2+2^2+3^2+...+(n+1)^2 = 1^2+2^2+3^2+...+n^2+(n+1)^2 = (1^2+2^2+3^2+...+n^2)+(n+1)^2 = n(n+1)(2n+1)/6+(n+1)^2 = (n+1)(n(2n+1)/6+(n+1)) = (n+1)((n(2n+1)+6(n+1))/6) = (n+1)((2n^2+n+6n+6)/6) = (n+1)(2n^2+7n+6)/6 = (n+1)(2n^2+4n+3n+6)/6 = (n+1)(2n(n+2)+3(n+2))/6 = (n+1)(n+2)(2n+3)/6.

Therefore, 1^2+2^2+3^2+...+n^2 = n(n+1)(2n+1)/6 for all n in the set of positive integers. ∎

• basis. S(1). 1^2 = 1 = 1(2)(3)/6. true.

Assume S(n). Prove S(n+1)

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

By induction hypothesis, the first group of terms

= n(n+1)(2n+1)/6

n(n+1)(2n+1)/6 + n^2+2n+1 = 1/6(2n^3 + 3n^2 + n + 6n^2+12n+6) = 1/6(2n^3 + 9n^2 + 13n +6)=1/6(n+1)(n+2)(2n+3) which is S(n+1).

• Let P(k) be the proposition that:-

1² + 2² + ------k² = k.(k + 1).(2k + 1) / 6

Consider P(1):-

LHS = 1² = 1

RHS = (1 x 2 x 3) / 6 = 1

Thus P(1) is true

Consider P(k + 1):-

1² + 2² + --k² + (k + 1)² = (k + 1).(k + 2).(2k + 3)/6

Now 1² +2² + ----k² = k.(k + 1).(2k + 1) / 6

Add (k + 1)² to both sides:-

LHS

1² + 2² + ---k² + (k + 1)²

RHS

k.(k + 1).(2k + 1) / 6 + (k + 1)²

[ k.(k + 1).(2k + 1) + 6.(k + 1)² ] / 6

[ (k + 1).[(k).(2k + 1) + 6(k + 1)] / 6

[ (k + 1).(2k² + 7k + 6 ] / 6

[(k + 1)(k + 2).(2k + 3) / 6

Thus P(k) true-->P(k + 1) true

and P(1) true

Therefore P(n) is true for all + ve integers.

• 1. base case: prove true for n=1

S(1)=1^2=1

[1(1+1)(2(1)+1)]/6=[2*3]/6=6/6=1

2. induction hypothesis, assume true for n=k

S(k) = 1^2 + 2^2 + ... +k^2 = [k(k+1)(2k+1)]/6

3. proof: prove true for n=k+1

S(k+1)=1^2 + 2^2 + ... + k^2 + (k+1)^2 = [k(k+1)(2k+1)]/6 + (k+1)^2 = [k(k+1)(2k+1)+6(k+1)^2]/6

then you simplify until you get it to equal:

[(k+1)(k+2)(2(k+1)+1)]/6

once you do that, you conclude "S(n) = 1^2 + 2^2 + ... +n^2 = [n(n+1)(2n+1)]/6 is true by induction."

• Anonymous

3 steps.

1-Show- show that the expression is true for n=1 (pretty much already done)

2-Assume- assume that the expression is true for n=k (k(k+1)(2k+1)/6=k^2

3-Prove- break the equation down using basic concepts from Algebra 1. Factoring, like terms, exponent addition/subtraction, etc.

I think the rest you can figure out.

• n = 1

S(1) = 1 = 1*2*3/6 = 1

verified for n = 1

Assume it holds for n = k

ie S(k) = k*(k+1)*(2k+1)/6

Let's investitage n = k + 1

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

= k*(k+1)*(2k+1)/6 + (k+1)^2

= (k+1)/6 * [ k*(2k+1) + 6*(k+1) ]

= (k+1)/6 * [ 2k^2 + 7k + 6 ]

= (k+1)/6 * [ (k+2)*(2k+3) ]

= (k+1) * (k+1+1) * (2[k+1]+1) / 6

= S(k+1)

verified for k+1

hence S(n) is true for all n

• Anonymous