2
$\begingroup$

I'm a high school student, and I'm stuck on part 2 of this question. I would like some hints (not a full solution) on how to approach it:

enter image description here1

The specific part of the question that confuses me is the significance of [Hint: The case $n=4$ is a good place to start.]. What about case $n=4$ makes it better over case $n=3$? Because I'm failing to see that.

What I've tried so far with case $n=4$ is that I've tried to show $((a+b+c+d)/4)^4 \geq abcd$ by expanding $(a+b+c+d)/4$. I don't think this is the right method though, for two reasons:

  1. It doesn't seem to use the fact that $n=4$: I could have done $n=3$, with $((a+b+c)/3)^3 \geq abc$.

  2. I don't see how I can generalize this method to an AM-GM inequality with any $n$ values.

So could someone give me a hint about the hint :)? I would really appreciate it if someone could explain how I could use this hint to solve this problem. Also, could you give me a hint only, and not a full solution? I still want solving the remaining problem to be a challenge.

Thanks in advance!

$\endgroup$
1
  • 2
    $\begingroup$ To prove this for any integer n, first prove by induction that this is true for some number 2^k. Then again by induction, show that it is true for 2^k-1, 2^k-2,.., n. This is called proof by forward-backward induction (by Cauchy). $\endgroup$
    – Alessio K
    Jan 25, 2020 at 9:31

3 Answers 3

5
$\begingroup$

As others have noted, $n=4$ is a natural starting point because of Cauchy's double-then-climb-down inductive strategy. The $n=3$ case is reasonably easy on its own, viz.$$x^3+y^3+z^3-3xyz=(x+y+z)(x^2+y^2+z^2-xy-yz-zx),$$where the quadratic factor is $\ge0$ by Cauchy-Schwarz, but e.g. $n=7$ isn't as easy as $n=8$. But I disagree with

There are many proofs, none of them are completely straightforward.

In particular, we can use a "normal" proof by induction that doesn't snake through the values of $n$ in a nonstandard way. Perhaps the simplest proof (if the intended audience doesn't know calculus), if we restate the problem as proving $\prod_ia_i=1\implies\sum_ia_i\ge n$ for positive $a_i$, is to arrange $n+1$ terms in the inductive step so $a_1\ge1\ge a_2$, whence$$\begin{align}(a_1-1)(1-a_2)&\ge0\\\implies a_1+a_2&\ge 1+a_1a_2\\\implies\sum_ia_i&\ge 1+\underbrace{a_1a_2+\sum_{i\ge3}a_i}_{\ge n\text{ by inductive hypothesis}}\\&\ge n+1.\end{align}$$Edit: come to think of it, this approach is even simpler, albeit with induction on the number of steps it takes to make all values equal, rather than on $n$.

$\endgroup$
2
$\begingroup$

The simple part is $n=2$, as it follows from $(\sqrt a-\sqrt b)^2\ge 0$.

Show how the case for $n=2^{k+1}$ follows from the case $2^k$. By induction, conclude that the claim holds for all powers of $2$.

Now use "downward induction" to reach arbitrary $n$ from the next highest power of $2$.

$\endgroup$
4
  • $\begingroup$ Thanks for the response. My question is, how would we prove this inequality holds for numbers that are not powers of 2? Because to my understanding, the AM GM inequality should hold for all real values of n. $\endgroup$
    – Ethan Chan
    Jan 25, 2020 at 9:17
  • $\begingroup$ @EthanChan You also have to show that, if it holds for some value of $n$, then it holds for all smaller values of $n$. $\endgroup$
    – bof
    Jan 25, 2020 at 10:05
  • $\begingroup$ @EthanChan That's the "downward induction" part. So if we "unroll" the inductions, the result for, say, $13$ follows along the "induction path" $1\to 2\to 4\to 8\to 16\to15\to14\to 13$. $\endgroup$ Jan 25, 2020 at 10:14
  • $\begingroup$ I see. Thank you! $\endgroup$
    – Ethan Chan
    Jan 25, 2020 at 10:35
0
$\begingroup$

Note that for any positives $a,$ $b$ and $c$ we have: $$\frac{a+b+c+\frac{a+b+c}{3}}{4}\geq\sqrt[4]{abc\cdot\frac{a+b+c}{3}}$$ Can you end it now?

$\endgroup$
2
  • $\begingroup$ Can down-voter explain us, why did you do it? $\endgroup$ Jan 25, 2020 at 20:59
  • $\begingroup$ It seems I have accidentally downvoted? Can you make a small edit to your post so I can undo this? Thanks! $\endgroup$
    – J. De Ro
    Jan 25, 2020 at 23:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .