Finding the inductive hypothesis

Question

I'm not sure what the inductive hypothesis is for this problem since there is a comparison symbol. I am supposed to prove by induction on n, that for all n > 1,

Please help!

Answer 1

You are not supposed to worry about whether there is an inequality/equality involved or not, in the statement given to you. All you need to do really , is to replace $n$ by $n+1$ in the given statement.

In this case, our statement is $\sum_{k=1}^n \frac{1}{k^2} < 2 - \frac 1n$. Just find all the $n$s in the above statement and replace them by $n+1$ to get $\sum_{k=1}^{\mathbf{n+1}} \frac 1{k^2} < 2 - \frac 1{\mathbf{n+1}}$.

So, your induction hypothesis is that the statement : $\sum_{k=1}^n \frac 1{k^2} < 2 - \frac 1n$. You assume this to be true. Call this statement $(1)$.

Now, using other standard facts, you want to prove the next statement, which is $\sum_{k=1}^{n+1} \frac 1{k^2} < 2 - \frac 1{n+1}$. Call this statement $(2)$.

Think about how you would go from $(1)$ to $(2)$. One idea is that the left hand side of $(2)$ is just the left hand side of $(1)$, increased by $\frac 1{(n+1)^2}$. So, to get the left hand side of $(2)$, we can add $\frac 1{(n+1)^2}$ to both sides of $(1)$, which will also be a true statement. This gives: $$ LHS(1) + \frac 1{(n+1)^2} < RHS(1) + \frac 1{(n+1)^2} \implies LHS(2) < 2 - \frac 1n + \frac 1{(n+1)^2} $$

Now, all you have to do, is show that $2 - \frac 1n + \frac 1{(n+1)^2}$ is less than the right hand side of $(2)$: $$ 2 - \frac 1n + \frac{1}{(n+1)^2} < 2 - \frac 1{n+1} \quad ? $$

To see this, note that $\frac 1n - \frac 1{n+1} = \frac 1{n(n+1)}$ by cross multiplication. Now, $n(n+1) < (n+1)^2$, therefore, $\frac 1{n(n+1)} > \frac 1{(n+1)^2}$ and therefore, $\frac 1n - \frac 1{n+1} > \frac 1{(n+1)^2}$. Transposing, $\frac 1n - \frac 1{(n+1)^2} > \frac 1{n+1}$.

Taking the negative of both sides and adding $2$ to both sides, then gives the $?$ inequality. Hence, the induction hypothesis is proved.

EDIT : To confirm,the base case is $1 \frac 14 < 1 \frac 12$ for $n = 2$, which is true.

Answer 2

Note that we have at $n=1$, $LHS=RHS$. At $n=2$, $LHS<RHS$ . Now let your equation be $(1)$. It is enough to prove the following: $$\frac{1}{(n+1)^2} < \frac{1}{n} - \frac{1}{n+1} = \frac{1}{n(n+1)}$$ as if we add it to equation $(1)$, we have the same equation $(1)$ for $n+1$. However, this is straightforward. Hence, we have proved it using induction.

We can make this argument stronger, since as $n$ approaches infinity, $LHS = \frac{π^2}{6}$ which is approximately $1.61$. This is the basel problem or the Riemann Zeta Function at s=2. Hence, we can fix $n=3$ in the $RHS$ and the argument would still hold.

Finally, induction is all about having a domino effect to prove a countabily infinite number of arguments. It has nothing to do with equalities. It is one of the most beautiful arguments in mathematics. A countable infinite here refers to Aleph nol cardinality. Hence, we can also use induction for rational numbers! I'll let you find that out by yourself. Cheers, mate!