mathematical induction?

Question

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?

Answer 1

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

Answer 2

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
Start with the definition of S(n+1):
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.

Answer 3

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. ∎

Answer 4

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).

Answer 5

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.

Answer 6

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."

Answer 7

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.

Answer 8

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

Answer 9

Substitute n+1 for n throughout, and simplify, and show that the result differs from the original result by only the additional term (n+1)^2.