Is this Proof by Induction a backwards proof?

99 Views Asked by At

let $P(n)$ be the statement that $1*1!+2*2!+...+n*n! = (n+1)! -1$

P(1) is true because $1*1! = (1+1)! - 1 = 1$

Assume $P(n)$. Shall show that $P(n+1)$ holds.

$1*1!+2*2!+...+n*n! + (n+1)(n+1)! = (n+2)! - 1 \\(n+1)! -1 + (n+1)(n+1)! = (n+2)! -1 \\(n+1)! + (n+1)(n+1)! = (n+2)! \\(n+1)! + (n+1)(n+1)! = (n+1)!(n+2) \\n+2=n+2$

Was this ok, or should I have started with the LHS and manipulated the LHS only so that eventually it equaled the RHS, (n+2)! - 1.

1

There are 1 best solutions below

0
On

Your proof would have been valid if you had stated

$1*1!+2*2!+...+n*n! + (n+1)(n+1)! = (n+2)! - 1 \iff \\(n+1)! -1 + (n+1)(n+1)! = (n+2)! -1 \iff \\(n+1)! + (n+1)(n+1)! = (n+2)! \iff \\(n+1)! + (n+1)(n+1)! = (n+1)!(n+2) \iff \\n+2=n+2$

(Although, aesthetically I hate those type of "meet in the middle" proofs. Although they can be handy for proving inequalities.)

Your proof, as it stands now, reads as though you are stating what is to be proven as a fact and you are attempting to prove the conclusion "n+2 = n+2".

Each step of a "meet in the middle" proof has to be equivalent (if and only if) to the previous. If any are only one way it is invalid.

$5 = -1 \\5 - 2 = -1 - 2 \\(5-2)^2 = (-1-2)^2 \\25 - 20 + 4 = 1 + 4 + 4 \\25 - 20 = 1 + 4 \\25 - 1 - 20 = 1-1 +4 \\24 - 20 = 4 \\20 - 20 = 0 \\20 = 20 $

is, of course, invalid. The error would be obvious if this were a direct "proof".