Proper way to make transition from $k$ to $k+1$ in proofs by induction

Question

First off my apologies for asking really simple questions, but I'm having some trouble wrapping my head around proof of induction when trying to prove a statement involving a natural number n holds for all values of n.

In the induction step lets assume the following simple example as found on this wikipedia page:

Proof the formula below for all positive integers.

In the wikipedia example inductive step. They ADD k+1 on the left side, but REPLACE k with k+1 on the right side. My book adds k+1 on both the left AND the right side. Example: Wikipedia starts the right side of the inductive step with:

So the wikipedia example replaced n with k+1. My book starts the right side of the inductive step with: $= \frac {k(k+1)}{2} + k+1$. So my book just added it to the right side. Now for this particular example it doesn't matter when you replace or add the k+1 on the right side. The outcome of the proof will be the same.

My question is if it EVER matters in proof of induction. If I want to prove Pn+1 is true assuming Pn is true. Should I just replace the n with n+1 on both sides, should I add it on both sides of the equation or does it never matter?

EDIT: Based on multiple answers I was able to get a clear understanding of how I should properly use proof of induction! Thanks a lot everyone!

Answer 1

You seem to be confusing two distinct things:

• The statement that we WANT to prove (i.e., $P_{k+1}$), but haven't proven yet.
• The steps used to obtain the statement that we want to prove.

For example, consider the following statement $P_n$:

$$ 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} $$

In order to obtain $P_{k+1}$ (the statement that we WANT to prove), we simply take the above statement and replace $n$ with $k+1$: $$ 1 + 2 + \cdots + (k+1) = \frac{(k+1)(k + 2)}{2} $$ Note that we haven't proven anything yet. All that we've done so far is given ourselves a goal for us to work towards.

Now when we actually try to perform valid logical manipulations to prove the above statement, we need to start with what we know. Indeed, we start by assuming that our induction hypothesis $P_k$ is true: $$ 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} $$ and then perform a valid manipulation, which is adding $k+1$ to both sides: $$ 1 + 2 + \cdots + k + (k+1) = \frac{k(k + 1)}{2} + (k+1) $$ Simplifying the right hand side, we obtain: $$ \frac{k(k + 1)}{2} + (k+1) = \frac{k(k + 1) + 2(k+1)}{2} = \frac{(k + 1)(k+2)}{2} $$ Thus, we've established that: $$ 1 + 2 + \cdots + k + (k+1) = \frac{(k + 1)(k+2)}{2} $$ which is exactly the statement $P_{k+1}$ that we wanted to prove. So we've performed the induction step correctly!

Answer 2

Actually the idea is that you start from the statement for $n$ that you assume true. Then you can do everything you want modifying it but it must remain true. In your case, for example, you add on the right and left side $n+1$ since when you have an equality $A=B$ also the following is true $A+n+1=B+n+1$. Then you have to rewrite the right factor to look like what you want. In particular $$ \frac{n(n+1)}{2}+n+1=(n+1)((n/2)+1)=(n+1)\frac{n+2}{2} $$ that is exactly the right side of your statement for $n+1$. I hope this clarified a bit what you are doing. Let me now if is not yet clear.

Answer 3

It does matter. However for this problem both methods amount to the same thing.

In induction, you prove a base case and then prove that a next case will be true. Depending on your problem, this can take a range of approaches, as long as the approach proves the next case.

Answer 4

In the induction step you assume that your statement holds for some $n$ and then prove that it also holds for $n + 1$.

In your particular example, the statement to prove is that $1 + 2 + \dots n = \frac{n(n+1)}2$. Assume this holds for some $n$. We want to show that it also holds for $n + 1$. So what we have to show is that $1 + 2 + \dots + n + (n + 1) = \frac{(n+1)(n+2)}2$ using our assumption.

Now there are two ways to do this. The first one is to take this equation we want to prove and try to reduce it to the statement with $n$ (which we assumed to be true). This is what you describe from Wikipedia.

The second way is to note that to get from $1 + 2 + \dots + n$ to $1 + 2 + \dots + n + (n + 1)$, we must add $n + 1$. So it is sufficient to show that if we add $n + 1$ to the right hand side as well, then we get our new right hand side for $n + 1$.

In some sense, the first way is working backwards (start from the assertion and try to get to your assumption) and the second way works forwards (start from the assumption and try to reach the assertion). Nevertheless, it proves the same result.