Is Induction or Deduction the Correct Approach?

[mtanti]

The whole question circles around how you prove that S(N) true ==> S(N+1) true

 

[quasar987]

You just use your ingenuity and try to find a way. For instance, for the statement

\sum_{i=1}^n i = \frac{n(n+1)}{2}

The statement S(N) is,

\sum_{i=1}^N i = \frac{N(N+1)}{2}

While S(N+1) is,

\sum_{i=1}^{N+1} i = \frac{(N+1)(N+2)}{2}

Assuming S(N) is true (i.e. assuming that the equality btw the left hand side and the right hand side holds), let us try to prove that S(N+1) is also true.

Let us add the number N+1 on both sides of the equation for S(N). It becomes,

(N+1)+\sum_{i=1}^N i = \frac{N(N+1)}{2}+(N+1) \ \ \ \mbox{(*)}

We can "incorporate" the (N+1) in the sumation notation in the following way:

(N+1)+\sum_{i=1}^N i = \sum_{i=1}^{N+1} i

While we can manipulate the right hand side this way:

\frac{N(N+1)}{2}+(N+1) = (N+1)\frac{N}{2}+(N+1) = (N+1)\left[ \frac{N}{2}+1 \right] = (N+1)\left[ \frac{N}{2}+\frac{2}{2} \right]=(N+1)\left[ \frac{N+2}{2}\right] = \frac{(N+1)(N+2)}{2}

Such that equation (*) can we rewriten as,

\sum_{i=1}^{N+1} i = \frac{(N+1)(N+2)}{2}

which is precisely the statement S(N+1).

 

[mtanti]

And this is a deductive proof right? So you prove that, assuming truth for S(N), S(N+1) is also true by deductive method? Because deductive proof works by showing that the left hand side is equal to the right hand side, and that is what you are doing when you show that

S(N+1) = (N+1)((N+1)+1)/2

Because N+1 fitted into the equation, it means that you can find S(N+1) too, assuming that S(N) is true. And you show that S(N) is true by finding a value which shows it is true.

Cool...

 

[quasar987]

I don't follow most of your reasoning but it sounds like you're getting a hang of it. Your turn now. Prove the following by induction:

\sum_{i=1}^{n}(2i-1)=n^2 \ \ \ \ \forall n\in\mathbb{N}

(The sum of the n first odd positive integers is n²)

 

[mtanti]

Hey man, I know how to prove by induction, I just don't know what I'm doing. Is it deductive or not?

RTP S(2n-1) = n^2

STEP 1: Prove that statement is true for n=1
2(1)-1 = 1^2
1 = 1
QED

STEP 2: Prove that if statement is true for n, it is also true for n+1
RTP S(2n+1) = (n+1)^2 [Is this what this step is all about?]

S(2n+1) = n^2 + n+1
RHS cannot be transformed into (n+1)^2, therefore S(n+1) will not work, therefore S(n) is not true.

QEDLESS

 

[Swapnil]

Hey man, I know how to prove by induction, I just don't know what I'm doing. Is it deductive or not?

RTP S(2n-1) = n^2

STEP 1: Prove that statement is true for n=1
2(1)-1 = 1^2
1 = 1
QED

STEP 2: Prove that if statement is true for n, it is also true for n+1
RTP S(2n+1) = (n+1)^2 [Is this what this step is all about?]

S(2n+1) = n^2 + n+1
RHS cannot be transformed into (n+1)^2, therefore S(n+1) will not work, therefore S(n) is not true.

QEDLESS

I think you are still a bit confused. I think it would help if you would stop using S(something) to mean two different things. You sometimes let S stand for summation and sometimes you let it stand for statement.

Here is the way you do the proof:

You first let your S(n) (the statement) stand for the given relationship (here instead of saying "S(n) = something" I will say "S(n) [=] something" since S(n) is a statement and not your typical algebraic relationship) i.e

S(n)\,[=]\,\sum_{i=1}^{n} 2i-1 = n^2

\Rightarrow 1 + 3 +...+ 2n-1 = n^2

Now we know that S(n+1) is the following (simply substitute "n+1" wherever you see "n")

S(n+1)\,[=]\,\sum_{i=1}^{n+1} 2i-1 = (n+1)^2

\Rightarrow 1 + 3 +...+ 2n-1 + 2(n+1)-1 = (n+1)^2

\Rightarrow 1 + 3 +...+ 2n-1 + 2n+1 = (n+1)^2

So to "expand" S(n) into S(n+1) the first thing we can do is add 2n+1 to both sides of S(n) i.e.

S(n)\,[=]\,1 + 3 +...+ 2n-1 + 2n+1 = n^2 + 2n + 1

Notice that (n+1)^2 = n^2 + 2n + 1 which is exactly what we have on the RHS. Thus we have in a way "derived" S(n+1) just from S(n). Thus, S(n) => S(n+1). Noiw since the base case obviously works, we have completed our inductive proof.

 

[Swapnil]

I think that your problem is that you think we just add the magic number "n+1" to both sides of S(n) and it should somehow lead us to S(n+1). That's not the case. We always have to add something that will take us one step closer to S(n+1), which in this case was the number "2n+1."

 

[Dragonfall]

Also, just for your information, mathematical induction can only be used to proved relationships which involve whole numbers.

Not true. If you prove S(x) is true for some real x, and if S(x) is true for some real t, then it is true for all x\in [t-\epsilon ,t+\epsilon ] with fixed epsilon, then it's true for all R.

I don't know how much more generalization this can take, but you should be able to do this for any metric space that's 'connected'.

 

[quasar987]

Hey, nice! Do you know of any classic proofs that can be conducted that way?

 

[HallsofIvy]

And this is a deductive proof right?

Yes, all mathematics proofs are deductive

So you prove that, assuming truth for S(N), S(N+1) is also true by deductive method? Because deductive proof works by showing that the left hand side is equal to the right hand side

That's one way a deductive proof works.

, and that is what you are doing when you show that

S(N+1) = (N+1)((N+1)+1)/2

Because N+1 fitted into the equation, it means that you can find S(N+1) too, assuming that S(N) is true. And you show that S(N) is true by finding a value which shows it is true.

Cool...

Yes, it is.

 

[Dragonfall]

Hey, nice! Do you know of any classic proofs that can be conducted that way?

Unfortunately I don't know of any that's not trivial or redundant.

 

[mtanti]

OK I got my mistake in the previous working... Sorry if I was so thick at the moment...

OK so all we do is show that if f(n) + [n+1]th term = f(n+1) then it shows that for a true value of f(n), f(n+1) will also be true.

I still wonder why you can say that... Sorry...

 

[0rthodontist]

Not true. If you prove S(x) is true for some real x, and if S(x) is true for some real t, then it is true for all x\in [t-\epsilon ,t+\epsilon ] with fixed epsilon, then it's true for all R.

I don't know how much more generalization this can take, but you should be able to do this for any metric space that's 'connected'.

The usual generalization (at least the generalization used in the proof of induction) is to a set that is well ordered under some relation--meaning every subset of the set has a minimal element under the relation. I guess what you're doing in what you're proposing is producing an infinite family of well ordered sets, each including those numbers for which the differences between each number and t are equivalent "modulo" epsilon, and using induction on those.

 

[Swapnil]

OK so all we do is show that if f(n) + [n+1]th term = f(n+1) then it shows that for a true value of f(n), f(n+1) will also be true.

I still wonder why you can say that... Sorry...

No No No... Its time that we start asking YOU questions instead of the opposite. We have answered the same exact question numerous times. Now its your job to figure out the answer.

Pick anyone of the responses that we gave you in response to your question. Read that response. If you don't understand what a certain part of that response means, then quote that response and then post it here. Make sure you tell us EXACTLY what part of the response you don't understand.