# An apparently harmless exercise concerning induction

I'm trying to solve Exercise 12 at page 14 from "A Concrete Introduction to Higher Algebra" by L. Childs. The text is the following.

Let $$b \in \mathbb{R}, b \ge 2$$. Prove that $$(b^n - 1)(b^n - b)(b^n -b^2)\cdots(b^n - b^{n-2}) \ge b^{n(n-1)}-b^{n(n-1)-1}$$ for all $$n \in \mathbb{N}, n \ge 1$$.

Two clarifications: I think the result holds for $$b \ge 1$$, I will assume $$n \ge 2$$.

The base case is $$n = 2$$. I have to show that $$b^2 - 1 \ge b^2 - b$$ and it is true for $$b \ge 1$$.

Suppose the result holds for $$n = k \ge 2$$, I want to show that the result holds for $$n = k + 1$$ too. I know that $$(b^k - 1)(b^k - b)(b^k -b^2)\cdots(b^k - b^{k-2}) \ge b^{k(k-1)}-b^{k(k-1)-1}$$ thanks to the inductive hypothesis. I want to show that $$(b^{k+1} - 1)(b^{k+1} - b)(b^{k+1} -b^2)\cdots(b^{k+1} - b^{k-1}) \ge b^{(k+1)k}-b^{(k+1)k-1}.$$ The left part is $$(b^{k+1} - 1)(b^{k+1} - b)(b^{k+1} -b^2)\cdots(b^{k+1} - b^{k-1}) = (b^{k+1} - 1)b(b^k-1)b(b^k-b)b(b^k-b^2)\cdots b(b^k-b^{k-2})= b^{k-1}(b^{k+1} - 1)(b^k-1)(b^k-b)(b^k-b^2)\cdots(b^k-b^{k-2}) \ge b^{k-1}(b^{k+1} - 1)(b^{k(k-1)}-b^{k(k-1)-1}) = b^{k^2+k}-b^{k^2+k-1}-b^{k^2-1}+b^{k^2-2}.$$ The right part is $$b^{(k+1)k}-b^{(k+1)k-1}= b^{k^2 + k} - b^{k^2 + k - 1}.$$ So I have to prove that $$b^{k^2+k}-b^{k^2+k-1}-b^{k^2-1}+b^{k^2-2} \ge b^{k^2 + k} - b^{k^2 + k - 1} \Leftrightarrow b^{k^2-2} \ge b^{k^2-1}$$ which is not true unfortunately.

It seems that the inductive hypothesis is not strong enough to prove the thesis.

Any help is appreciated.

• Have you tried simplifying the expression and proving this directly, not using induction? – Danica Apr 10 at 21:27
• It works directly, but I would like to prove it by induction because I think that was the original goal. – Riccardo17 Apr 10 at 21:36

Change variable to $$c = \frac1b$$. The inequality at hand (the version for $$b \ge 2)$$ is equivalent to

$$\prod_{k=2}^n (1-c^k) \ge 1 - c\quad\text{ for }\;n \ge 2, c \in \left(0,\frac12\right]$$

To prove this by induction, we will use a stronger form of induction statement.

For $$n \ge 1$$ and $$c \in (0,\frac12]$$, let $$\mathcal{S}_n$$ be the statement

$$\mathcal{S}_n :\quad \prod_{k=2}^n (1-c^k) \ge \frac{1-c}{1-c^n}$$

When $$n = 1$$, LHS is an empty product and evaluates to $$1 =$$ RHS, so $$\mathcal{S}_1$$ is true.

Assume $$\mathcal{S}_{n}$$ is true, we have

$$\prod_{k=2}^{n+1} (1-c^k) = (1-c^{n+1})\prod_{k=2}^n (1-c^k) \ge (1-c^{n+1})\frac{1-c}{1-c^n}$$

Since $$c \in (0,\frac12]$$, we have $$(1-c^{n+1})^2 > 1 - 2c^{n+1} \ge 1 - c^n \implies \frac{1-c^{n+1}}{1-c^n} > \frac{1}{1-c^{n+1}}$$ This leads to $$\prod_{k=2}^{n+1} (1-c^k) > \frac{1-c}{1-c^{n+1}}$$

and hence $$\mathcal{S}_n \implies \mathcal{S}_{n+1}$$. By induction, $$\mathcal{S}_n$$ is true for all $$n \ge 1$$.

As a result,

$$\prod_{k=2}^n (1-c^k) \ge \frac{1-c}{1-c^n} > 1 - c\quad\text{ for }\; n \ge 1, c \in \left(0,\frac12\right]$$

As a side note, the conjecture about $$b \ge 1$$ doesn't work in general. For example, the inequality for $$n = 3$$ fails when $$b < \frac{\sqrt[3]{9+\sqrt{69}} + \sqrt[3]{9-\sqrt{69}}}{\sqrt[3]{18}} \approx 1.324717957244746$$.

• Very clear. I'm wondering if it is possible to formulate a stronger but easier to prove initial statement without changing variable. For the side note I made confusion: I meant that I think the inequality holds for $b \ge 1$ asymptotically in $n$ but it is another story. – Riccardo17 Apr 11 at 9:16
• @Riccardo17 w/o changing variable, the induction statement here is equivalent to $(b^n - 1)(b^n-b)\cdots(b^n - b^{n-2}) \ge \frac{b^n}{b^n-1}(b^{n(n-1)} - b^{n(n-1)-1})$ and for any fixed $b > 1$, if the inequality fails at $n = m$, then it fails for all $n > m$. So the inequality does not hold asymptotically in $n$ for $b \ge 1$. However, the $b \ge 2$ part can be improved to $b \ge b_*$ for some $b_* \in (1,2)$ (not sure about the exact value). – achille hui Apr 11 at 10:40