# Homework Help: Fuzzy on induction

1. Sep 27, 2009

### Kasperloeye

1. The problem statement, all variables and given/known data

Hey I'm a little fuzzy on how the induction-proof really works.. and am therefore a little stuck.. I know some parts.. but I need a kick in the right direction.. you don't have to solve it.. just give me a hint or a kick as I said ^^ that would be nice

2. Relevant equations
Which nonnegative integers makes the following statement true.. a induction proof would be the best way of solving it i think.. but how do I get started.. and what would be the base theorem..?
n²<=n!

3. The attempt at a solution
I can logically see what values that is needed.. but help.. please..

2. Sep 27, 2009

### CompuChip

Generally, when you have some statement like "for all n, X is true", a proof by induction consists of two steps. First, you have to show that for some simple case (usually n = 0 or 1, depending on the question), X is true. Then you assume that X is true for all integers n up to some given value n0, and you prove that under that assumption, X is also true for n0 + 1.

The reasoning is then as follows: you have checked by hand that it is true for n = 1. You have proven that if it is true for n0 = 1 (which it is), then it is true for n = n0 + 1 = 2. So it is true for n = 2. Also, you have shown that if it is true for n = 2, it is true for n = 3. Since it is true for n = 2, it holds for n = 3. Similarly, it is true for n = 4, and for n = 5, and so on.

Note that proof by induction is a convenient way (once you are used to it) to prove such statements "for all n", but it doesn't help you to find the statement. So if instead of "prove that the nth derivative is ....formula...." you get "derive and prove a formula for the nth derivative", you will first need to come up with a hypothesis by some other way. Once you have the hypothesis, you can make it into a theorem and try to prove it by induction.

In your particular problem, you could consider a statement like "For all n >= 2, n2 <= (n!)".

3. Sep 27, 2009

### Kasperloeye

Hehe that's where it get's funny.. because n>= 2, n²<=n! is like 2²<=2! 4 <= 2 .. so it has to n /= 2

So Basis should be n=4 since

4²<=4!
16 <=24

SO: For n=k, k²<=k!

but if we take it with n= k+1 it's (k+1)² <=(k+1)!
(k+1)² <= (k+1)(k!)
(k+1) <= k!
but our hypothasis says k^2 <= k!, and because k+1 <= k^2 (for k>=4) then
k+1 <= k^2 <= k!.

right??