# Proof by induction

1. Dec 11, 2009

### jersiq1

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

prove by induction that
$$\frac{1}{n^2} < \frac{1}{n(n-1)}$$

2. Relevant equations

n/a

3. The attempt at a solution

Let
$$P(n):\frac{1}{n^2} < \frac{1}{n(n-1)}$$

Since P(1) is undefined, the base case is P(2)
$$P(2) = \frac{1}{2^2} < \frac{1}{2(2-1)}$$
$$P(2) = \frac{1}{4} < \frac{1}{2}$$

Therfore P(n) is true for all n>1

Inductive Step
Assume $$P(k)$$ is true.

$$P(k):\frac{1}{k^2} < \frac{1}{k(k-1)}$$

I know what I need my inequality to look like for $$k+1$$ I am just having problems getting there. my $$k+1$$ will look like:
$$P(k+1):\frac{1}{(k+1)^2} < \frac{1}{(k+1)[(k+1)-1]}$$
after simplification:
$$P(k+1):\frac{1}{(k+1)^2} < \frac{1}{(k+1)(k)}$$
So I know where I need to be. Consider this is just side work.

So for $$k+1$$ I can rewrite an expansion on the LHS as:
$$\frac{1}{k^2+2k+1}$$
And based on my inductive step the RHS of the inequality is:
$$\frac{1}{[k(k-1)]+2k+1}$$

And this is where I am hitting the block. Try as I might, I can't see any steps to take to make $$\frac{1}{[k(k-1)]+2k+1}$$ equivalent to $$\frac{1}{(k+1)(k)}$$

I am worried that I may have set up my induction incorrectly though.

Last edited: Dec 11, 2009
2. Dec 11, 2009

### Staff: Mentor

The line above isn't true. All you have done is establish that the proposition is true for your base case.
I would approach this in a different way. 1/k^2 < 1/((k -1)k) is equivalent to k^2 > k(k - 1). We can safely assume that all factors are nonnegative. If you can prove by induction that k^2 > k(k - 1), then you will have proved the equivalent statement, the one in your problem.

3. Dec 11, 2009

### jersiq1

Thanks, that does make it rather easy.
Just so I am sure I can write this correctly, the justification for equating the two identical inequalities is that k(k-1) > 0 Is that because of the base case starting with n>1 or because induction is on $$\mathbb{N}$$

4. Dec 11, 2009

### Staff: Mentor

If a < b, and both a and b are positive, then 1/a > 1/b. For your original inequality it's reasonable to assume that n > 1 (and hence positive); otherwise you would be dividing by 0 when n = 1. For your induction proof, you are proving it for all n >= 2.

Generally speaking (but with caveats) if a < b, then 1/a > 1/b. The caveat is that both a and b have to be the same sign. For example, 2 < 3 and 1/2 > 1/3. OTOH, -1 < 2, but 1/(-1) > 1/2 is not true.