3
$\begingroup$

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.

enter image description here

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: enter image description here

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!

$\endgroup$
  • $\begingroup$ I don't understand your question. Proof by induction will depend on what you are trying to prove, for each situation there might be a different approach. $\endgroup$ – Aaron Maroja Sep 8 '14 at 19:31
  • $\begingroup$ You are right, my apologies. I'm trying to prove whether statements involving natural number n is true for all values of n. $\endgroup$ – Joey Sep 8 '14 at 19:40
4
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Thanks a lot Adriano! Based on your answer and the others' I managed to not only get rid of the confusion in my example, but get rid of some confusion I had of other examples as well! I am extremely grateful for the effort you and the others do for new students like me! $\endgroup$ – Joey Sep 8 '14 at 19:59
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.