Proof by induction: conversion to equal expressions

Question

Lets suppose that I am trying to prove: $$1^2+...+n^2 = 1/6n(n+1)(2n+1)$$ via induction, but I am unable to convert (for sake of argument) $$1/6k(k+1)(2k+1)+(k+1)^2$$ to $$1/6(k+1)(k+2)(2k+3)$$ to prove that $$1^2+...+k^2+(k+1)^2 = 1/6k(k+1)(2k+1) + (k+1)^2$$ so instead I manage to convert both of them to $$1/6(2n^3+9n^2+15n+6)$$ showing that they are equal. Would that be enough to consider this proof by induction complete are is my reasoning wrong?

Welcome to Mathematics Stack Exchange. I think it would be clearer if you wrote $.../6$ or $\frac16...$ instead of $1/6...$ — J. W. Tanner, Oct 04 '19 at 14:36
You are mixing $n$ and $k$ here. Note that you have an obvious factor $k+1$ in your workings and you have made an error in your final formula because it isn't zero when $n=-1$ (constant coefficient should be $13$). — Mark Bennet, Oct 04 '19 at 14:48

score 1 · Accepted Answer · answered Oct 04 '19 at 14:32

Your logic is backwards: you started with the conclusion and derived something true, rather than starting with what you know and deriving the conclusion.

For example, $0 = 1$ implies $0=0$ by multiplying both sides by zero, but that doesn't mean that $0=1$ is true!

If you want to use this line of reasoning, you need to argue that your steps are reversible. Then from the equation you derive, you can deduce that the statement you derived it from (the goal of the induction step) is true.

score 1 · Answer 2 · answered Oct 04 '19 at 14:50

We need to prove the induction step, that is

$$1^2+...+k^2+(k+1)^2 =\frac{(k+1)(k+2)(2k+3)}6$$

and using the induction hypotesis, that is

$$1^2+...+k^2 =\frac{k(k+1)(2k+1)}6$$

you have properly derived

$$1^2+...+k^2+(k+1)^2 =\frac{k(k+1)(2k+1)}6+(k+1)^2=\frac{k(k+1)(2k+1)+6(k+1)^2}6$$

now we need a few algebra to obtain

$$k(k+1)(2k+1)+6(k+1)^2=(k+1)(2k^2+k+6k+6)=(k+1)(2k^2+7k+6)$$

and since

$$(2k^2+7k+6)=(k+2)(2k+3)$$

we are done.

Your last step obtained converting all by the variable $n$ is not so much clear. You should complete the proof using the variable $k$ till the end to be more clear.

Dr. Sonnhard Graubner · Answer 3 · 2019-10-04T14:44:50.830

0

You have to show that $$(n+1)^2+\frac{1}{6}n(n+1)(2n+1)=\frac{1}{6}(n+1)(n+2)(2n+3)$$ Can you show this? Factorizing this we get $0$.

edited Oct 04 '19 at 14:44

answered Oct 04 '19 at 14:34

Dr. Sonnhard Graubner

95,283

"Factorizing this we get $0$" — sounds like you're making the same mistake as the OP: starting with what you want to be true and deriving a true conclusion, rather than starting with something known/assumed and deriving what you want to be true. – Clive Newstead Oct 04 '19 at 14:40
This is totally wrong what you wrote, this is the proof step in the induction proof. – Dr. Sonnhard Graubner Oct 04 '19 at 14:43
The other steps are easy. – Dr. Sonnhard Graubner Oct 04 '19 at 14:43
Yes it should be $2n+3$, sorry, my father was gone yesterday. – Dr. Sonnhard Graubner Oct 04 '19 at 14:45
@DrSonnhardGraubner: Maybe I misinterpreted what you wrote, but your answer sounds like you're suggesting starting with the equation in your answer and deriving $0=0$ from it. – Clive Newstead Oct 04 '19 at 16:12
No i have used that $$s_n+a_n=s_{n+1}$$ via induction. – Dr. Sonnhard Graubner Oct 04 '19 at 16:14
That part is fine. I agree with you that the OP has to show that the equation in your question is true. It's the "Factorizing this we get 0" that I think is the issue. It sounds like you want to derive $0=0$ from the equation in your question, which does not suffice to prove that the equation in your question is true. – Clive Newstead Oct 04 '19 at 16:38

Proof by induction: conversion to equal expressions

3 Answers3