Yup, there are times in life when you want to go below the average even if it sounds like an unfavorable move on the surface.
Life is all about experience isn't it?, and how are you going to experience if you do not explore?
At above average, the glass is only half full. It has all the tools to be complete like a pot with mud, seeds, and water:
To bring it up to brim you need to draw in experiences from below the average as well. A bit of warmth, and that's when the purpose gets served of hosting something complete and alive.
As in these pictures, it could be that, above the average lies logic and intelligence of increasing magnitude, and below lies something beyond, something radiant. When intelligence is side-stepped, the heart speaks. And when you meet a friend, your heart speaks because you can be your dumb self. And what the heart speaks, that is the truth, that is life.
And so i wind back the current chain of thoughts a bit that led me to this marvelous truth of life, yet again 😉
Enter problem 1.9 Concrete Mathematics
"$ P(n) : x_1 *... * x_n \le \left( \dfrac{x_1+...+x_n}{n} \right)^n$ if $x_1,x_2,..x_n \ge 0 $
a. By setting $x_n = \left( \dfrac{x_1 + · · · + x_{n-1}}{n - 1} \right)$, prove that $P(n)$ implies $P(n - 1)$ whenever $n > 1$.
b. Show that $P(n)$ and $P(2)$ imply $P(2n)$.
c. Explain why this implies the truth of $P(n)$ for all $n$
Solving this problem as per steps a., b., and c. above is pretty easy as worked here.
But a. gives us the liberty to use the average value $x_{avg} = \dfrac{x_1 + .. + x_{n-1}}{n-1}$ as $x_n$ to prove that $P(n) \implies P(n-1).$
Fine, $P(n) \implies P(n-1)$ when $x_n = x_{avg}$. But, what if $x_n$ is any value either greater or less than $x_{avg}$ ?
So lets save $x_n$ from this restriction and give it some freedom, let it be whatever it wants to be as long as it stays positive and real 😉.
In such a case, we can express $x_n$ as a function of other ordinals as $c*\left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right)$ where $c$ can be any constant positive and real.
This way we come up with a value for $x_n$ which can be arbitrary but with a denominator to help us simplify the algebra a bit.
Now if we start with $P(n)$:
$x_1 * ... x_n \le \left( \dfrac{x_1 + ... + x_n}{n} \right)^n \curvearrowright$
$ (x_1 * ... x_{n-1}) * c*\left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right) \le \left( \dfrac{x_1 + ..+ x_{n-1} + c*\left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right)}{n}\right)^n \curvearrowright$
$ (x_1 * ... x_{n-1}) * c*\left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right) \le \left(\dfrac{n - 1 + c}{n}\right)^n * \left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right)^n \curvearrowright$
$ x_1 * ... x_{n-1} \le \dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n* \left(\dfrac{x_1 + ... + x_{n-1}}{n-1}\right)^{n-1}$
If $P(n-1)$ is true, we should be able to prove that:
$\dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n \ge 1$
Above average
Now, if we consider $x_n \gt x_{avg}$, then, $c-1 \gt 0 \curvearrowright$
$\dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n = \dfrac{1}{c*n^n}*\left(n + (c-1)\right)^n$
Remeber the binomial theorem where $(a+b)^n = a^n + n *a^{n-1}*b + ... $
Its pretty easy to derive the first two terms as described here in this wikipedia section
Hence we have
$\dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n = \dfrac{1}{c*n^n}*\left(n^n + n*n^{n-1}*(c - 1) + \alpha \right)$ where $\alpha \gt 0 \curvearrowright$
$\require{cancel} \dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n = \dfrac{\cancel{1} + \bcancel{c} - \cancel{1}}{\bcancel{c}}*\dfrac{\cancel{n^n}}{\cancel{n^n}} + \dfrac{\alpha}{c*n^n} \curvearrowright$
$ \dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n = 1 + \dfrac{\alpha}{c*n^n} $
Below Average
If $x_n \lt x_{avg}$, then, $c-1 \lt 0$ which means we will have some negative terms in the binomial series expansion and it would get a bit tricky to really check the validity of the inequality:
$\dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n \ge 1$, wouldn't it?
And as you see, sometimes, above the average could be the easy part.
So, what do we do? As we are blessed with computers today, we can just plot the value of this expression for various $n > 2$ and $c < 1$
We can write some quick python code to do our plot and we get something like:
And so, we can see it in the trend that the function $\dfrac{1}{c}*\left(\dfrac{n - 1 + c}{n}\right)^n$ is always $ \ge 1$
But how can we prove it without analyzing the negative products in the binomial series further?
For the inequality to hold
$\left(\dfrac{n - 1 + c}{n}\right)^n \ge c \leadsto \left(\dfrac{n - 1 + c}{n}\right) \ge \sqrt[n]{c}$
If we let $ c = d^n $, then we need $\left(\dfrac{n - 1 + d^n}{n} \right) \ge d \curvearrowright$
we need $ X(n) : d^n + n \ge n*d + 1$
Also since $c \lt 1$ when $x_n \lt x_{avg}$, $d$ must also be $\lt 1$, To simplify, let $b=\dfrac{1}{d}$ where $b \gt 1$
Then we can re-write $ X(n): \left(\dfrac{1}{b}\right)^n + n \ge \dfrac{n}{b} + 1 \leadsto : \dfrac{1 + n*b^n}{b^n} \ge \dfrac{n + b}{b} \curvearrowright$
$\require{cancel} X(n): \dfrac{1 + n*b^n}{b^{\cancel{n} * (n - 1})} \ge \dfrac{n + b}{\cancel{b}} \leadsto : 1 + n * b^n \ge n * b^{n-1} + b^n \curvearrowright$
$X(n): (n - 1)*b^n \ge n*b^{n - 1} - 1$ where $b > 1$
Lets use induction to prove $X(n)$ as above, and instead of considering it as $X(n)$, lets consider it as $X(b) \forall b \gt 0, n \gt 0$
Base case:
When $ b = 1$, l.h.s = r.h.s = $1+n$
Inductive Step:
Lets assume $X(b)$ is true, and check l.h.s of $X(b+1)$
l.h.s of $X(b+1)$ is $(n - 1) * (b + 1)^n = (n - 1) * (b + 1) * (b + 1)^{n-1} \curvearrowright$
$X(b+1)_{l.h.s} = (n*b + n - b - 1) * (b+1)^{n-1}$
$= n * (b + 1)^{n-1} + (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
$X(b + 1)_{l.h.s} = n * (b + 1)^{n-1} + \beta$ where $\beta = (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
$X(b + 1)_{l.h.s} = X(b + 1)_{r.h.s} + \beta$ where $\beta = (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
Since $b \gt 1$ and $n \gt 0, \beta \gt 0$
Thus we can safely and soundly conclude that when $X(b)$ is true, $X(b+1)$ is also true.
Conclusion
In fact, we didn't even had to use $X(b)$ at all to prove $X(b+1)$, We just proved it for $X(1)$ and we showed $X(b)$ is true $\forall{b}\ge 2$
But i wonder if there is a simpler proof which does not assume $x_n$ to be $x_{avg}$ 😃
Substituting $x_n$ with $\left(\dfrac{x_1 + · · · + x_{n-1}}{n - 1}\right)$ in $P(n)$, we get
$x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ x_1+...+x_{n-1} + \dfrac{x_1 + ... + x_{n-1}}{n-1} }{n} \right)^n$ $\curvearrowright$
$x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ (n-1) * (x_1+...+x_{n-1}) + 1 * (x_1 + ... + x_{n-1})}{(n-1) * n} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ (n - \cancel{1} + \cancel{1}) * (x_1 + ... + x_{n-1})}{(n-1) * n} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ \cancel{n} * (x_1 + ... + x_{n-1})}{(n-1) * \cancel{n}} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * \cancel{x_n} \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^{n-1} * \cancel{x_n}$
remember, we chose $x_n$ as $x_{avg}$
Hence, we have:
$ x_1 * .. * x_{n-1} \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^{n-1} \rightarrow P(n-1)$
Thus when $x_n = x_{avg}, P(n) \implies P(n-1)$
b.
First lets try to assert $P(2)$. From $P(n)$ the r.h.s of $P(2)$ would be:
$\left( \dfrac{x_1 + x_2}{2} \right)^2 = \dfrac{ \left(x_1 - x_2\right)^2 + 4 * x_1 * x_2 }{4}$ $\curvearrowright$
$\left( \dfrac{x_1 + x_2}{2} \right)^2 = \left( \dfrac {x_1 - x_2}{2} \right)^2 + x_1*x_2$ $\curvearrowright$
$\left( \dfrac {x_1 - x_2}{2} \right)^2 = \left( \dfrac{x_1 + x_2}{2} \right)^2 - x_1*x_2$
Since $ \left( \dfrac {x_1 - x_2}{2} \right)^2 \ge 0 \forall x_1, x_2 \in \Re $, it $\implies$
$x_1*x_2 \le \left( \dfrac{x_1 + x_2}{2} \right)^2$
Thus we have $P(2) $
Now since we have established $P(2)$, lets assume $P(n)$ is true and look at the l.h.s for $P(2n)$ :
$(x_1 * ... * x_n) *(x_{n+1} * ... * x_{2n})$
Breaking $(x_1 * ... * x_n)$ and $(x_{n+1} * ... * x_{2n})$ as two independent terms and applying $P(2)$ we have:
$x_1 * ... * x_{2n} \le \left( \dfrac{(x_1 * ... * x_n) + (x_{n+1} * ... * x_{2n})}{2} \right)^2 $
Applying $P(n)$ on $(x_1 * ... * x_n)$ and $(x_{n+1} * ... * x_{2n})$ in the r.h.s, we have:
$x_1 * ... * x_{2n} \le \left( \dfrac{1}{2} * \left( \left( \dfrac{x_1 + ... + x_n}{n} \right)^n + \left( \dfrac{x_{n+1} + ... + x_{2n}}{n} \right)^n \right) \right)^2 \curvearrowright$
$x_1 * ... * x_{2n} \le \left( \dfrac{1}{2} *\left( \dfrac{x_1 + ... + x_n + x_{n+1} + ... +x_{2n}}{n} \right)^n \right)^2 \curvearrowright$
$x_1 * ... * x_{2n} \le \left( \dfrac{x_1 + ... +x_{2n}}{2n} \right)^2n$
And thus we have $P(2n)$ when $P(n)$ and $P(2)$ are true.
c.
From a. and b. we can prove $P(n)$ for all $n$ this way:
$P(2) \implies P(4) \implies P(3) \implies P(6) \implies P(5)$ etc
We can write some quick python code to do our plot and we get something like:
But how can we prove it without analyzing the negative products in the binomial series further?
For the inequality to hold
$\left(\dfrac{n - 1 + c}{n}\right)^n \ge c \leadsto \left(\dfrac{n - 1 + c}{n}\right) \ge \sqrt[n]{c}$
If we let $ c = d^n $, then we need $\left(\dfrac{n - 1 + d^n}{n} \right) \ge d \curvearrowright$
we need $ X(n) : d^n + n \ge n*d + 1$
Also since $c \lt 1$ when $x_n \lt x_{avg}$, $d$ must also be $\lt 1$, To simplify, let $b=\dfrac{1}{d}$ where $b \gt 1$
Then we can re-write $ X(n): \left(\dfrac{1}{b}\right)^n + n \ge \dfrac{n}{b} + 1 \leadsto : \dfrac{1 + n*b^n}{b^n} \ge \dfrac{n + b}{b} \curvearrowright$
$\require{cancel} X(n): \dfrac{1 + n*b^n}{b^{\cancel{n} * (n - 1})} \ge \dfrac{n + b}{\cancel{b}} \leadsto : 1 + n * b^n \ge n * b^{n-1} + b^n \curvearrowright$
$X(n): (n - 1)*b^n \ge n*b^{n - 1} - 1$ where $b > 1$
Lets use induction to prove $X(n)$ as above, and instead of considering it as $X(n)$, lets consider it as $X(b) \forall b \gt 0, n \gt 0$
Base case:
When $ b = 1$, l.h.s = r.h.s = $1+n$
Inductive Step:
Lets assume $X(b)$ is true, and check l.h.s of $X(b+1)$
l.h.s of $X(b+1)$ is $(n - 1) * (b + 1)^n = (n - 1) * (b + 1) * (b + 1)^{n-1} \curvearrowright$
$X(b+1)_{l.h.s} = (n*b + n - b - 1) * (b+1)^{n-1}$
$= n * (b + 1)^{n-1} + (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
$X(b + 1)_{l.h.s} = n * (b + 1)^{n-1} + \beta$ where $\beta = (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
$X(b + 1)_{l.h.s} = X(b + 1)_{r.h.s} + \beta$ where $\beta = (b * (n - 1) - 1) * (b + 1)^{n-1} \curvearrowright$
Since $b \gt 1$ and $n \gt 0, \beta \gt 0$
Thus we can safely and soundly conclude that when $X(b)$ is true, $X(b+1)$ is also true.
Conclusion
In fact, we didn't even had to use $X(b)$ at all to prove $X(b+1)$, We just proved it for $X(1)$ and we showed $X(b)$ is true $\forall{b}\ge 2$
But i wonder if there is a simpler proof which does not assume $x_n$ to be $x_{avg}$ 😃
Standard Proof
a.Substituting $x_n$ with $\left(\dfrac{x_1 + · · · + x_{n-1}}{n - 1}\right)$ in $P(n)$, we get
$x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ x_1+...+x_{n-1} + \dfrac{x_1 + ... + x_{n-1}}{n-1} }{n} \right)^n$ $\curvearrowright$
$x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ (n-1) * (x_1+...+x_{n-1}) + 1 * (x_1 + ... + x_{n-1})}{(n-1) * n} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ (n - \cancel{1} + \cancel{1}) * (x_1 + ... + x_{n-1})}{(n-1) * n} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ \cancel{n} * (x_1 + ... + x_{n-1})}{(n-1) * \cancel{n}} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * x_n \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^n$ $\curvearrowright$
$ \require{cancel} x_1 * .. * x_{n-1} * \cancel{x_n} \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^{n-1} * \cancel{x_n}$
remember, we chose $x_n$ as $x_{avg}$
Hence, we have:
$ x_1 * .. * x_{n-1} \le \left( \dfrac{ x_1 + ... + x_{n-1}}{n-1} \right)^{n-1} \rightarrow P(n-1)$
Thus when $x_n = x_{avg}, P(n) \implies P(n-1)$
b.
First lets try to assert $P(2)$. From $P(n)$ the r.h.s of $P(2)$ would be:
$\left( \dfrac{x_1 + x_2}{2} \right)^2 = \dfrac{ \left(x_1 - x_2\right)^2 + 4 * x_1 * x_2 }{4}$ $\curvearrowright$
$\left( \dfrac{x_1 + x_2}{2} \right)^2 = \left( \dfrac {x_1 - x_2}{2} \right)^2 + x_1*x_2$ $\curvearrowright$
$\left( \dfrac {x_1 - x_2}{2} \right)^2 = \left( \dfrac{x_1 + x_2}{2} \right)^2 - x_1*x_2$
Since $ \left( \dfrac {x_1 - x_2}{2} \right)^2 \ge 0 \forall x_1, x_2 \in \Re $, it $\implies$
$x_1*x_2 \le \left( \dfrac{x_1 + x_2}{2} \right)^2$
Thus we have $P(2) $
Now since we have established $P(2)$, lets assume $P(n)$ is true and look at the l.h.s for $P(2n)$ :
$(x_1 * ... * x_n) *(x_{n+1} * ... * x_{2n})$
Breaking $(x_1 * ... * x_n)$ and $(x_{n+1} * ... * x_{2n})$ as two independent terms and applying $P(2)$ we have:
$x_1 * ... * x_{2n} \le \left( \dfrac{(x_1 * ... * x_n) + (x_{n+1} * ... * x_{2n})}{2} \right)^2 $
Applying $P(n)$ on $(x_1 * ... * x_n)$ and $(x_{n+1} * ... * x_{2n})$ in the r.h.s, we have:
$x_1 * ... * x_{2n} \le \left( \dfrac{1}{2} * \left( \left( \dfrac{x_1 + ... + x_n}{n} \right)^n + \left( \dfrac{x_{n+1} + ... + x_{2n}}{n} \right)^n \right) \right)^2 \curvearrowright$
$x_1 * ... * x_{2n} \le \left( \dfrac{1}{2} *\left( \dfrac{x_1 + ... + x_n + x_{n+1} + ... +x_{2n}}{n} \right)^n \right)^2 \curvearrowright$
$x_1 * ... * x_{2n} \le \left( \dfrac{x_1 + ... +x_{2n}}{2n} \right)^2n$
And thus we have $P(2n)$ when $P(n)$ and $P(2)$ are true.
c.
From a. and b. we can prove $P(n)$ for all $n$ this way:
$P(2) \implies P(4) \implies P(3) \implies P(6) \implies P(5)$ etc
pycode
import matplotlib.pyplot as plt import numpy as np n = [2, 3, 5, 8, 13, 21] c = np.linspace(0.1, 5.0, 10000) for j in n: k = (((j-1+c)/j)**j)/c l = "n="+str(j) plt.plot(c, k, label=l) k = c/c plt.plot(c, k, label="y=1") plt.xlabel('c') plt.ylabel('(((n-1+c)/n)**n)/c') plt.title("Blah plot") plt.legend() plt.show()
