PDA

View Full Version : A question on proof by mathematical induction


Yusf
Nov 14, 2015, 05:29 PM
The steps for proof for mathematical induction induction for summation of a series are listed in my book as:
1. prove that it is true for n=1.
2. assume that it is true for n=k.
3. thus prove that it is true for n=k+1

Now it is step 2 and 3 that bothers me. We assume that the expression is true for n=k. So the expression can also be equal to r. And r can be equal to k+1. So is we assume step 2, we assume step 3 as well, there is must not be a need to prove it.

In other words, for step 2, k can equal any positive integer, so we are assuming the thing that we should have proved.

I hope I have clearly explained why I am confused. Obviously there is a logical explanation for this, which I hope will be given by a reader.

Thank you for taking time to read this.

ebaines
Nov 16, 2015, 05:59 AM
The thing is that it may not be true for any random value of k. For example, suppose that we are asked to prove that the sum of 1 to n is n - you probably already know that this sum actually equals n(n+1)/2, so the hypothesis is wrong. But it is certainly true for n = 1. Next we assume it's true for some value of n=k, and seek to prove that it must also be true for n=k+1:

\sum _{i=1}^{k+1} i = \sum _{i=1}^k i+ (k+1) = k + (k+1 ) = 2k+1

Since 2k+1 does not equal n=k+1, we have disproved the hypothesis. So you see we didn't jump from an assumption that if true for n= k it must also be true for n=k+1.

Yusf
Nov 16, 2015, 06:36 PM
It always takes a few word's from you to clear all my confusions! Thanks. :-)