Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-09-16 13:37:02

Identity
Member
Registered: 2007-04-18
Posts: 934

Induction

Proposition:

for all n ≥ 2.

Proof: If n=2, we have

or
, which is true.
Assume:
               
for all 2 ≤ n ≤ k
Taking n=k, we have
               

Multiplying by k+1, we  have
               

               


I can't get k+1 in the base of the RHS! Help plz

Offline

#2 2007-09-16 14:57:59

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Induction

Estimates are a mathematician's best friend, especially if you are studying analysis.  Don't be trying to show equality.  Rather, show inequality:

(k+1)k^k < (k+1)(k+1)^k

This should be fairly straightforward.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2007-09-16 20:54:19

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Induction

Thanks heaps, could you please help me on another proof?

Exercise 2.9. Prove that if n ≥ 12 then n can be written as a sum of 4’s and 5’s. For example, 23 = 5 + 5 + 5 + 4 + 4 = 3 · 5 + 2 · 4. [Hint. In this case it will help to do the cases n = 12, 13, 14, and 15 separately. Then use induction to handle n ≥ 16.]

If n = 5a + 4b for some integers a and b, what will n+1 be equal to? n+1 = 5c+4d? Then 5c+4d-1=5a+4b... I don't think I'm getting anywhere. dunno

Offline

#4 2007-09-17 03:24:00

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Induction

So the trick here is that 5 - 4 = 1.  That is, if you take out one 4, and you add in one 5, you will get +1.

3*4 + 2*5 = 22
2*4 + 3*5 = 23

Now that is not the entire problem, but it's part of it.  What if you have 5*x, i.e. only 5's?  The above trick won't work.  But what will?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#5 2007-09-17 03:34:07

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Induction

Hmm, if n = 5x, then n+1 = 5(x-3)+4(4)
            n = 4x, then n+1 = 4(x-1)+5
         if n = 5x+4x, then n+1 = 5(x-1)+4(x+1)

So do I have to make cases for n= 5x, 4x, 5x+4x and evaluate them separately? Do they cover all possible cases?

Last edited by Identity (2007-09-17 03:36:42)

Offline

#6 2007-09-17 03:47:03

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Induction

Nah, just think about it this way:

case 1: n contains at least 1 4.
case 2: n contains no 4's.

Now get n+1 in each case.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2007-09-17 06:11:35

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Induction

Thanks for your help, I've finished the induction chapter

Offline

Board footer

Powered by FluxBB