Prove by Induction: \frac{1}{n^2} < \frac{1}{n(n-1)}

• jersiq1
In your problem, k and k - 1 are both nonnegative for any k >= 2, so you don't have to worry about the caveat.
jersiq1

Homework Statement

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

n/a

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:
jersiq1 said:

Homework Statement

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

n/a

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
The line above isn't true. All you have done is establish that the proposition is true for your base case.
jersiq1 said:
Inductive Step
Assume $$P(k)$$ is true.

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

Now here, I know where I need to go, so I am not going to write my final result out. 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.

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.

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}$$

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.

1. What is the purpose of using induction in this proof?

The purpose of using induction in this proof is to show that the statement is true for all values of n, not just a specific value or a finite set of values. This allows us to prove the statement for an infinite number of cases.

2. How does the induction step work in this proof?

In the induction step, we assume that the statement is true for some value of n, and then use that assumption to prove that the statement is also true for the next value of n. This creates a chain of logical steps that demonstrates the truth of the statement for all values of n.

3. Why is the base case important in this proof?

The base case is important because it establishes the truth of the statement for the smallest possible value of n. This serves as the starting point for the induction step and allows us to build upon it to prove the statement for all values of n.

4. How do we use the inequality \frac{1}{n^2} < \frac{1}{n(n-1)} in this proof?

We use this inequality as the basis for our induction step. By assuming that the statement \frac{1}{n^2} < \frac{1}{n(n-1)} is true for some value of n, we can manipulate it algebraically to show that the statement is also true for the next value of n. This allows us to extend the truth of the statement to all values of n.

5. Can this proof be applied to other similar statements involving fractions?

Yes, this proof can be applied to other similar statements involving fractions, as long as certain conditions are met. For example, the statement must have a base case that can be proven true, and the induction step must involve manipulating an inequality in a way that preserves its truth. With these conditions, the proof by induction can be used to prove a variety of statements involving fractions.

Replies
9
Views
606
Replies
10
Views
711
Replies
4
Views
319
Replies
6
Views
1K
Replies
11
Views
720
Replies
3
Views
802
Replies
11
Views
529
Replies
13
Views
2K
Replies
1
Views
1K
Replies
9
Views
2K