can you perform induction by assuming k and k+1 and showing difference is correct.

154 Views Asked by At

for example

LHS: $1+2+3+4+5... =$ RHS: $n(n+1)/2$ is usually proved by base case 1 and assuming that it is true for $k$, and showing that $k(k+1)/2 + k+1$ is the same as $(k+1)(k+1+1)/2$.

However can we assume that the statement is true for k and true for k+1, and since $((k+1)(k+1+1)/2) - (k(k+1)/2)$ is $k+1$, it shows that the RHS always produces the correct difference. And since the base case is true, and the difference is always correct, by induction the RHS formula always holds.

Is this a valid proof by induction?

1

There are 1 best solutions below

3
On

For this specific case, the two approaches (showing the result for $k$ implies the result for $k+1$, and showing the formulae for $k$ and $k+1$ differ by $k+1$) happen to be equivalent.

However, in general this approach is not valid. Assuming the thing you are trying to prove, and deducing a true statement from it, does not constitute a proof. You have to go the other way: start from something you know to be true, and deduce what you are trying to prove. Sometimes you can just reverse the steps of your non-proof to get a valid proof, but often the argument will not be reversible.