$a_1, a_2, ..., a_{95}$ are positive reals. Show that $\displaystyle \sum_{k=1}^{95}{a_k} \le 94+ \prod_{k=1}^{95}{\max{\{1,a_k\}}}$
Problem
Source: Taiwan NMO 2006
Tags: inequalities, induction, function, inequalities proposed
fuzzylogic
21.03.2006 20:43
It's clear that if $A$ is a finite set of non-negative reals, then $1+\sum_{x\in A} x\le \prod_{x\in A}(1+x)$.
$\sum_{i=1}^n a_i = n+ \sum_{i=1}^{n}(a_i -1) = n+ \sum_{a_i\le1}(a_i -1) +\sum_{a_i>1}(a_i -1)$
$\le n + \sum_{a_i>1}(a_i -1) \le (n-1)+ \prod_{a_i>1}a_i = (n-1) + \prod_{i=1}^{n}{\max{\{1,a_i\}}}$
silouan
14.11.2006 17:20
fuzzylogic wrote: $\le n+\sum_{a_{i}>1}(a_{i}-1) \le (n-1)+\prod_{a_{i}>1}a_{i}= (n-1)+\prod_{i=1}^{n}{\max{\{1,a_{i}\}}}$ Why this ?Is it true?
scorpius119
30.12.2006 04:44
Let $b_{k}=\max \{ 1,a_{k}\}$, so that
\[\sum_{k=1}^{95}a_{k}\leq \sum_{k=1}^{95}b_{k},\ 94+\prod_{k=1}^{95}\max \{ 1,a_{k}\}=94+\prod_{k=1}^{95}b_{k}\]
So we will be done if we can prove that
\[\sum_{k=1}^{95}b_{k}\leq 94+\prod_{k=1}^{95}b_{k}\]
knowing that $b_{k}\geq 1$ for each $k$. Of course, this suggests
\[\sum_{k=1}^{n}b_{k}\leq n-1+\prod_{k=1}^{n}b_{k}\]
is true for any positive integer $n$. We show that this is in fact true, using induction. The base case is clearly true. For the inductive step,
\[n+b_{1}b_{2}b_{3}\cdots b_{n+1}=n+b_{1}b_{2}b_{3}\cdots b_{n}+b_{1}b_{2}b_{3}\cdots b_{n}(b_{n+1}-1)\]
\[\geq 1+(b_{1}+b_{2}+b_{3}+\cdots+b_{n})+b_{1}b_{2}b_{3}\cdots b_{n}(b_{n+1}-1)\geq b_{1}+b_{2}+b_{3}+\cdots+b_{n+1}\]
where we have simply used $b_{n+1}\geq 1,\ b_{1}b_{2}\cdots b_{n}\geq 1$ for the last step. This proves the inequality for any positive integer $n$; in particular, it works for $n=95$.
Lovasz
30.12.2006 10:46
A simple induction works also.
littletush
30.10.2011 07:13
if $a_i\le 1$ then $LHS=\sum_{k=i}a_k+a_i\le\sum_{k=i}a_k+1$ RHS remains unchanged. so let us assume $a_i\ge 1$ notice that $L-R$ is a linear function for all $a_i$ so when $a_i=1$,it attains minimum $94$ QED