Is Induction or Deduction the Correct Approach?

  • Thread starter mtanti
  • Start date
  • Tags
    Induction
In summary: S(n+1) is true... that S(n+2) is true... that S(n+3) is true... etc.Then you can be sure that S is true for all numbers n, n+1, n+2, n+3 etc.This is because we know that the statement S is true for some number n and then we show that it is also true for the next number. Now that we know it is true for the next number, we can use the same argument to show that it is true for the next number after that, and so on. And because we can keep doing this, it means that the statement S is true for all numbers, not just n but also
  • #36
mtanti said:
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

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

[tex] \Rightarrow 1 + 3 +...+ 2n-1 = n^2[/tex]

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

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

[tex] \Rightarrow 1 + 3 +...+ 2n-1 + 2(n+1)-1 = (n+1)^2[/tex]

[tex] \Rightarrow 1 + 3 +...+ 2n-1 + 2n+1 = (n+1)^2[/tex]

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.

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

Notice that [tex](n+1)^2 = n^2 + 2n + 1[/tex] 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.
 
Last edited:
Mathematics news on Phys.org
  • #37
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."
 
  • #38
Swapnil said:
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 [tex]x\in [t-\epsilon ,t+\epsilon ][/tex] 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'.
 
Last edited:
  • #39
Hey, nice! Do you know of any classic proofs that can be conducted that way?
 
  • #40
mtanti said:
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.
 
  • #41
quasar987 said:
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.
 
  • #42
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...
 
  • #43
Dragonfall said:
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 [tex]x\in [t-\epsilon ,t+\epsilon ][/tex] 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.
 
Last edited:
  • #44
mtanti said:
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.
 

Similar threads

Replies
8
Views
2K
Replies
5
Views
3K
Replies
28
Views
4K
Replies
7
Views
8K
Replies
26
Views
7K
Replies
22
Views
4K
Back
Top