$\textbf{Question:}$ Prove using induction that the following inequality holds for all positive integers $n$:

$$\dfrac{(1+a_1)(1+a_2)\cdots(1+a_n)}{1+a_1a_2\cdots a_n}\leq 2^{n-1},$$ where $a_1,a_2,\dots ,a_n\geq 1$.

$\textbf{Attempted (Incorrect) Solution:}$ Base Case: $\dfrac{(1+a_1)}{(1+a_1)}=1=2^0=2^{1-1}$. Assume we have $\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)}{1+a_1a_2\cdots a_k}\leq 2^{k-1}$ for some positive integer $k$. Clearly, $\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)}{1+a_1a_2\cdots a_ka_{k+1}}\leq\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)}{1+a_1a_2\cdots a_k}\leq 2^{k-1}$, so $\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)(1+a_{k+1})}{1+a_1a_2\cdots a_ka_{k+1}}=\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)}{1+a_1a_2\cdots a_ka_{k+1}}+\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)a_{k+1}}{1+a_1a_2\cdots a_ka_{k+1}}\leq 2^{k-1}+\dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)a_{k+1}}{1+a_1a_2\cdots a_ka_{k+1}}\leq 2^{k-1}+ \dfrac{(1+a_1)(1+a_2)\cdots(1+a_k)a_{k+1}}{a_1a_2\cdots a_ka_{k+1}}\leq 2^{k-1}+ \dfrac{2^k(a_1a_2\cdots a_k)a_{k+1}}{a_1a_2\cdots a_ka_{k+1}}=2^{k-1}+2^k=3\cdot2^{k-1}\not\leq 2^k.$

I've tried a couple of different approaches, but none of them have panned out. I feel like I might be missing some key insight/trick. Any hints/suggestions would be greatly appreciated. Thanks!



With $b_k = a_k a_{k+1} \ge 1, \quad c_k = a_k + a_{k+1}-1 \ge 1$,

$(1+a_k)(1+a_{k+1}) = 1+(c_k+1) + b_k \le (1 + b_k) + (1 + b_k c_k)$
and $b_kc_k \ge b_k = a_k a_{k+1}$

So split the LHS of the inductive step into two sums...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.