Arbitrary function is true when n = 1

[danne89]

Suppose a statement P(n) about an arbitrary function is true when n = 1. Suppose also that for any positive integer m such that P(m) is true, P(m+1) is also true. Then P(n) is true for every positive integer n

I cannot understand this method! If you can prove P(m) is true, why bother?? Isn't it enough to only prove P(m)?

 

[matt grime]

That's badly phrased, it ought to read IF P(m) is true, then P(m+1) is true. Thus we a priori do not know it is true, merely that if it is true then the successor is true. Now, since P(1) is true, this means that P(2) is true, which in turn implies P(3) and so on.

Example: Define a sequence a_n by a_1=1, and a_r = a_r +2.

Now, take the statement P(n):= { the term a_n is even}.
For this proposition, IF P(m) is true, then P(m+1) is true, so the inductive hypothesis is satisfied, however P(m) is always false.

 

[danne89]

So if, and only if, P(m+1) is true, also P(m) is true. But it don't seem easier to prove P(m+1) then P(m)

 

[HallsofIvy]

The point is: You prove: If P(n) is true for SOME SPECIFIC n, then it is true for n+1.

Saying "P(n) is true for SOME SPECIFIC n" is different from saying "P(n) is true for all n" which is the conclusion.

Of course, knowing "IF P(n) is true for SOME SPECIFIC n, then it is true for n+1." doesn't help if you don't know P(n) IS true for some specific n. That's why you need to prove P(1) is true.

It might help to use a different letter for the "specific" n:
To prove P(n) is true for all n:
1) Prove P(1) is true
2) Prove "If P(N) is true (for SOME N) then P(N+1) is true".

If we've done that we know (by 1) P(1) is true. Then (by 2) P(2) is true. Now (by 2 again) P(3) is true. Now, (by 2 again) P(4) is true...

 

[danne89]

Ahh. I think I see.

The Power rule when n=1 is true:
du^n/dx = n * u^n-1 * du/dx = 1 * 1 * du/dx = du/dx
And also when n=2:
du^2/dx = 2 * u * du/dx

Conclusion: du^n/dx = n * u^n-1 * du/dx

This's hard stuff. Perphas it's easier if one has some logic symbols...

 

[dextercioby]

Okay,it's not difficult at all.
$$\frac{du^{n}(x)}{dx} =n \ u^{n-1} \frac{du}{dx}$$
-----------------------||------------------------------------

You have chacked the validity for "n=1".Now apply the method of mathematical induction
1.Suppose that for arbitrary "n" is valid the conclusion:
$$\frac{du^{n}(x)}{dx} =n \ u^{n-1} \frac{du}{dx}$$(1)

Then,knowing (1) to be true,u need to prove that
$$\frac{du^{n+1}(x)}{dx} =(n+1) \ u^{n} \frac{du}{dx}$$(2)
--------------------------||----------------------------------

Use product rule (for differentiation) and the fact that:
$$u^{n+1}=u\cdot u^{n}$$(3)

and then simply use (1).The result,(2),will come out very easily.

Daniel.

 

[danne89]

Ah.

We want to prove P(n) = $$\frac {d(u^n)}{dx}=nu^{n-1} \frac {du}{dx}$$
P(1)=$$\frac{du}{dx}= 1 * u^0 * \frac {du}{dx}$$ Thus, P(1) is true.

Now, assume that P(m) is true: P(m)=$$\frac {d(u^m)}{dx}= m * u^{m-1}*\frac{du}{dx}$$

And then you must prove that P(m) implies P(m+1). This can you do with the power rule, for you're assuming it's correct.
P(m+1) = $$\frac {d(u^{m+1})}{dx} = \frac {d(u^m * u)}{dx} = u * \frac{d(u^m)}{dx} + u^m * \frac{du}{dx} = u * m * u^{m-1} * \frac{du}{dx} + u * \frac{du}{dx} = (m+1)u^m * \frac{du}{dx}$$

P(1) $\Longrightarrow$ P(2) ... P(1) is indeed true, and thus also P(2).
P(2) $\Longrightarrow$ P(3)

And so on...

 

[dextercioby]

That's right.You got it...

Daniel.

 

[matt grime]

So if, and only if, P(m+1) is true, also P(m) is true. But it don't seem easier to prove P(m+1) then P(m)

The truth of P(m+1) need tell you nothing about P(m).

And you are missing (at this point, though perhaps later in the thread you get it) the fact that we use the *assumed* truth of P(m) to *deduce* the truth of P(m+1). In the example I gave P(m) is false, for any m, but if we assume it true then P(m+1) is true by deduction:

if a_m is even then since a_{m+1} = a_m + 2, it must be that a_{m+1} is even. Ie P(m) implies P(m+1). But in the example I gave a_m is odd for all m.

 

[dextercioby]

The real trick in this math.induction is obviouls checking the validity for an arbitrary (preferably small,usually "+1") value of the parameter "n"...If you went ahead and proved that P(n)->P(n+1),that values nothing,as P(1) may be false...

Daniel.