Why only 2 Weighted Medians at most?

It is intuitive to observe that in a distinct ordering of numbers, there are at most two medians.If the number of elements is odd, i.e. $2n-1$, then $n^{th}$ element is the median.
Whereas, if the number of elements is even, i.e $2n$, then $n^{th}$ and $(n+1)^{th}$ elements form the median.

Apart from median, there is also a concept called "weighted median".

The Definition 

In a given distinct ordering of pairs $\{(i_1 ,w_1) , (i_2, w_2) .. , (i_n, w_n)\}$:
------> Let  $i$ represent any arbitrary identity of a given element; $w$ represents the weight of that element in the sequence; and $W$ the sum of weights of all the elements
------> Then, an element $i_m$ is a weighted median if $\displaystyle\sum_{1 \le j \lt m} w_j \le \frac{W}{2}$ and $\displaystyle\sum_{m \lt j \le n} w_j \le \frac{W}{2}$

The Interpretation

One good use of weighted median is to compute the median of all the values when there are multiples/repetitions of same values in the sampled data.
So if you have $n$ values with average repetition $w_{avg}$ unordered, the median could be computed at $O(n.w_{avg})$.
But if you organize or have the data as distinct values and their repetitions, the complexity to find the median could come down to $O(n)$

Let's see why this is so:

After expanding an ordering of the form: (Lets refer to this as abridged ordering)

 $\{(i_1 ,w_1) , (i_2, w_2) .. , (i_n, w_n)\}$ .....

to an ordering of the form: (lets call this expanded ordering)

 $\{i_1, i_1,...(w_1times), i_2, i_2, ....(w_2 times), ...., i_n, i_n, ... (w_n times) \}$

The total number of elements in the ordering would be:

$\displaystyle\sum_{1\le j \le n} w_j = W$.

Now we can easily say that the median of such an ordering would be $(\frac{W+1}{2})^{th}$ element if $W$ turns out to be odd.
And if its even, the median comprises of $(\frac{W}{2})^{th}$and $(\frac{W}{2} + 1)^{th}$elements.
Let a given repetition of $i_m$ be the median in the above expanded ordering, and lets also consider $W$ to be odd.
Then, the number of elements in the expanded ordering before and after the selected instance of $i_m$ must exactly be $W/2$.
Note that, for any element other than median, this property will not hold good.
Now if we extract out the copies of $i_m$ on its left, and right, if any, we can establish that the number of  non $i_m$ elements before and after $i_m$ is at most $W/2$.
Hence, if we calculate the weighted median of abridged ordering, it would be same as the median of the expanded ordering.
Similar argument can be made for when $W$ is even, and also the special case when such ordering has two distinct medians $i_m$ and $i_{m+1}$
From this analysis on using weights as repetitions, it is easy to see, that like median, the weighted medians can also be at most two.

The observation

But what if we focus on just the plain simple definition of weighted median without interpreting the weights as repetitions or such, and were to "observe" that at most, there can just be two weighted medians.... How would we establish that fact? Well, its not too hard.
Let $i_m$ be a weighted median in a given abridged ordering, then,

$\displaystyle\sum_{1 \le j \lt m} w_j + w_m + \displaystyle\sum_{m \lt j \le n} w_j = W$

Let $A = \displaystyle\sum_{1 \le j \lt m} w_j$, and $B = \displaystyle\sum_{m \lt j \le n} w_j$

  Then $A + w_m + B = W$ and by definition of weighted median, $A \le W/2$ and $B \le W/2$

Now, if we assume that: $w_m + B \le W/2$,  then we can claim that $w_{m-1}$ is also a weighted median.

This is because: $A \le W/2 \implies A - w_{m-1} \le W/2$ and of course by our assumption, we have $w_m + B \le W/2$

We have three relations to satisfy here: $1: A + w_m + B = W; 2: w_m + B \le W/2;$ and $3: A \le W/2$. 

All the three can be satisfied if and only if $4: A = W/2$ and $5: w_m + B = W/2$

Given that we already have weighted medians $w_{m-1}$ and $w_m$, the requirements in 4: and 5: above make it impossible to have any other weighted median.

Similar argument can also be made assuming that $A + w_m \le W/2$

For me this understanding proved to be more fun than actually writing the R-Select code to find out the weighted median itself, and hence come these notes 😀Though, i actually ended up describing the algorithm here 😛

2-D Peak-A-Proof

Hmm 😵.. Capacity for proofs... how important is that?

No logic is sound unless it is proved. The ability to prove is a testament to one of the three things:

 a) clarity of thought,

 b) loudness of mouth,

 c) willingness to self deceive 😛.

But more often than not, i guess its useful when its a); c) is not bad either, for it counter balances its other opposite, which is self doubt 😉

Somewhere between self doubt and self deceit lies self confidence, right? Not sure of b) but who knows, its probably used pretty widely, or? 😆

Ahem ahem... course correction.. back to the utility of proofs...
Take for example the rather simple 2-D Peak finding problem.
The 2-D Peak finding problem:

From a given n-by-n matrix A, find a (i.e., any) number A(i, j) such that all valid elements in A at positions A(i-1, j), A(i+1, j), A(i, j-1), A(i, j+1) are less than or equal to A(i, j).

Valid element means that the position computed is a valid legal position in the matrix.

For example: A(-1, 0) is NOT a valid element.

Simply put, an element is a peak, when the elements if any, immediately above, below, to the left, and to the right of it, are less than or equal to the given element.

In the example 5-by-5 matrix below, the peak elements are highlighted.

60	100	103	80	95
125	120	108	101	45
130	30	93	90	156
115	40	98	65	125
75	50	96	55	25

The Divide and Conquer algorithm(s) to efficiently find "a" peak is(are) rather simple, but, is the proof of their correctness as simple?
Well, i guess it varies from person to person. But for some reason, i have this inherent discomfort with anything more than one dimension.
And i get the urge to write about it as i have a feeling there maybe a few more confused souls like me who feel dazed thinking in more than one dimension 😛.

i tried for several hours to come up with a less than $O(n^2)$ algorithm, but just could not.

Started looking up for hints and tried the....
1-D Peak finding problem:
A peak in an array A means any A(i) such that both A(i-1) and A(i+1) are less than or equal to A(i).
For the beginning and end elements of the array, A(0) is a peak if A(1) ≤ A(0) and A(end) is a peak if A(end-1) ≤ A(end). Find such a peak from the array A.

1-D Peak finding algorithm
"A" (i.e. any) peak in this array can be found in O(logn) time using the following strategy:
1. Take a middle element, A(m) and check if it is a peak.If so, return A(m).
2.  If not, either A(m+1) or A(m-1) or both would be greater than A(m)
3. Continue with step 1 on the right half, if A(m+1) >A(m)
    Continue with step 1 on the left half, if A(m-1) > A(m)
    If both A(m-1), and A(m+1) are greater than A(m), either half is fine.
Is this algorithm correct? Seems trivial enough to prove so.

[proof:1-D Peak finding algorithm]
Suppose A(m) is not a peak and A(m+1) > A(m).
In this case, A(m+1) will be a peak unless its own right neighbor, A(m+2) > A(m+1).
Lets assume A(m+2) meets this condition. Inductively, for A(m+2) to not be a peak, A(m+3) > A(m+2) and it can go on and on, only till the end of the array where the end element will turn out to be a peak.
Hence, when we follow the half where A(m+1) > A(m), we are guaranteed to find a peak.
We can argue similarly for the case when A(m-1) > A(m).
[proof:end]

Surprisingly so, this new found wisdom on the 1-D case got me no where with the 2-D case, and finally i looked up the algorithm 😁
However, i still could not convince myself very easily that the 2-D algorithm i looked up is actually correct.
Guess this is always the case with borrowed analysis, because it is less of an analysis and more of an assurance.

Anyways putting a stop to the sob, here is the most simple of the divide and conquer algorithms for the 2-D case:
O(nlogn) 2-D Peak finding algorithm
1. Find the maximum element of the middle column, let it be A(i, m). 
  If its a peak, return it and terminate.
2.a) If A(i, m-1) >= A(i, m) and A(i, m+1) ≤ A(i, m); then recurse in the left half of matrix.
2.b) Else If A(i, m+1) > A(i, m) and A(i, m+1)  ≤= A(i, m); then recurse in the right half of matrix.
2.c) Else If A(i, m-1) >= A(i, m) and A(i, m+1)  >= A(i, m); then recurse in either left or right half. (i.e., either of the halves is guaranteed to have a peak)
3. If the recursion reduces the matrix to a single column, just return the max of that column and terminate.

Sounds neat and simple to code up, but is the algorithm correct?
How do we go about its correctness? It was a bit of mind muddling experience for me, because for once in the evening i thought i got the proof but couldn't really write it down. And when i tried to write it down before bed, i couldn't really come up with the proof again.. Wonder if the evening was a moment of self deceit or a volatile intuition 🤔. Well, so i decided to give it a go in the morning instead when luckily i guess i could reason the correctness correctly.

So here is a proof for the above binary search algorithm for the 2-D peak:
i changed my original proof a bit starting with the base case first. This way, it is simpler to understand and takes fewer words i think.
[proof:O(nlogn) 2-D Peak finding algorithm]
Consider the base case (Step 3), a single column and n rows of  elements. Lets call this column as c.
Its easy to see that the max of that column is a "peak" in that 1 column matrix. Lets call this peak as p.
Now, lets unwind the recursion, and add another column, c+1 of n elements to this matrix.
p ceases to be a peak in the new 2 column matrix only if column c+1 has an element greater than p in the same row as p.
But, Step 2.a) in the above algorithm ensures that not only the one next to p, but, all of the elements in column c+1 are less than p if column c+1 was skipped out of the search.
Fine, lets unwind a bit more, and add another column, c-1 of n elements to this matrix.
p ceases to be a peak in the new 3 column matrix only if column c-1 has an element greater than p in the same row as p.
However, Step 2.a) ensured that all the elements in column c-1 are indeed less than p if column c-1 was skipped out of the search.
Hence, inductively we can prove that when the algorithm hits the base case, it always finds a peak which is valid for the undivided input matrix
[proof:end]

The complexity of this algorithm is O(nlogn).
If you look at the design of this algorithm, you will notice, the main ingredient is to use the middle column as a virtual valley with the knowledge that the half next to this column has at least one element greater than any of the elements in this virtual valley, and hence there is a guarantee to find a peak in that particular half.

Now lets looks at the O(n) algorithm:
O(n)  2-D Peak finding algorithm

The O(n) algorithm extends this valley building effort both across the middle column as well as the middle row, and recurses into one of the quadrants where a peak is guaranteed to be found.
The algorithm goes as below:
1. Find the maximum element among all the elements of the middle row, $m_r$ and middle column, $m_c$
    If the maximum is at the intersection of the row and column, it is definitely a peak, so return it and terminate.
2. If the maximum is a peak, return it and terminate.
3. If the maximum is not a peak, recurse is the quadrant where adjacent neighbor of the maximum is greater than the maximum.
4. When recursion is left with only one row, return the max of that row and terminate. Or, if the recursion is left with only one column, return that max of that column and terminate. Or, if the recursion is only left with one element, that one element must be the peak, return it, and terminate.

Bit more details on step3
i am just writing more details on step3 to clarify and maybe also to aid the proof which is coming up.
3.a. If the maximum A($m_r$, j) is in the middle row, and j > $m_c$, and A($m_r$ + 1, j) > A($m_r$, j), then recurse in the quadrant bounded by rows $m_r$ +1 to end, and columns $m_c$ + 1 to end.Below 7 by 7 table gives an example of this case:
$m_c$ = $m_r$ = 4, maximum is A(4, 5) = 4520.
But A(5, 5) = 4610 > A(4, 5), Hence we recurse in the bottom right quadrant.

1923	3317	1784	4236	126	526	2583
4060	1068	1667	1263	3989	2461	4342
2764	139	4552	4029	502	2764	653
1347	2172	1614	2852	4520	4305	2199
4780	353	2606	1504	4610	3475	4515
1581	1132	719	38	1396	4285	4456
2607	3458	1651	3426	1078	4388	559
3328	2332	42	3865	378	3989	3959

3.b. Else if the maximum A($m_r$, j) is in the middle row, and j > $m_c$, and A($m_r$ - 1, j) > A($m_r$, j), then recurse in the quadrant bounded by rows 0 to $m_r$ -1, and columns $m_c$ + 1 to end. Below table gives an example of this case:
$m_c$ = 2, $m_r$ = 2, maximum is A(2,  3) = 4456.
But A(1, 3) = 4515 > A(2, 3), Hence we recurse in the top right quadrant.

4610	3475	4515
1396	4285	4456
1078	4388	559
378	3989	3959

Similarly it follows for other cases as below...
3.c. Else If the maximum A($m_r$, j) is in the middle row and j < $m_c$ , and A($m_r$ - 1, j) > A($m_r$, j), then recurse in the quadrant bounded by rows 0 to $m_r$ -1, and columns 0 to $m_c$ -1 
3.d. Else if the maximum A($m_r$, j) is in the middle row and j < $m_c$ , and A($m_r$ + 1, j) > A($m_r$, j), then recurse in the quadrant bounded by rows $m_r$ +1 to end, and columns 0 to $m_c$ -1 
3.e. Else if the maximum A(i, $m_c$) is in the middle column and i < $m_r$, and A(i, $m_c$ - 1) > A(i, $m_c$), then recurse in the quadrant bounded by rows 0 to $m_r$ -1  and columns 0 to $m_c$ -1
3.f. Else if the maximum A(i, $m_c$) is in the middle column and i > $m_r$, and A(i, $m_c$ - 1) > A(i, $m_c$), then recurse in the quadrant bounded by rows $m_r$ + 1 to end, and columns 0 to $m_c$ -1
3.g. Else if the maximum A(i, $m_c$) is in the middle column and i < $m_r$, and A(i, $m_c$ + 1) > A(i, $m_c$), then recurse in the quadrant bounded by rows 0 to $m_r$ -1  and columns $m_c$ + 1 to end.
3.h. Else if the maximum A(i, $m_c$) is in the middle column and i > $m_r$, and A(i, $m_c$ + 1) > A(i, $m_c$), then recurse in the quadrant bounded by rows $m_r$ + 1 to end, and columns $m_c$ + 1 to end.
       

Now that we stated the algorithm, rather elaborately, lets try to prove it by starting with base case.

[proof: O(n)  2-D Peak finding algorithm]

Consider the base case when only one row $r$ and columns $c_x$ to $c_y$ are left.

The maximum of that row, say, A(r,j) is the peak of that one row, r.

Lets unwind the recursion and add back the row r-1 to the array.

A(r, j) ceases to be a peak only if A(r-1, j) > A(r, j)

And steps 3.a, 3.d, 3.f, 3.h are the ones responsible for peeling off rows above.

Because of preconditions in the those steps, not only  A(r-1, j), but for all c such that $c_x$ < c < $c_y$; A(r-1, c) ≤= A(r, j)

On similar lines, the proof can be extended to the case when we add back row r+1, as well as when the base case is a column.

[proof:end]

Aiming high above average ain't a good aim at all

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}$ 😃

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()

Just eat the pizza, don't slice it

And even if you do, do not try to estimate how many maximum number of slices can be made by $n$ cuts.

Well, at least keep 3 A4 sized rough sheets with you, cause that's how many i scribbled on trying to solve this maximum number of slices problem 😀

The problem appears in 'Concrete Mathematics' as:
'How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?'
or
'What is the maximum number Ln of regions defined by n lines in the plane?'

Well, if you slice the pizza the way you usually do, it looks like $2n$ doesn't it? with every slice having a bit of the rounded hard to chew topping less edge

So, slicing the pizza is kind of an unnatural example, or should we say that math rather itself is a bit unnatural to people like me?

Turns out you can slice the pizza this way too

Well, the color of the pizza changed, that's because my 4.5 year old daughter jumped on to my couch and wanted it this way.. As with most guys who have a girl child, i, too must admit that i haven't really figured out why she likes pink from age 3, but anyways its not that relevant for cutting exotic pizza slices

Now, the explanation offered in the book to establish a recurrence relationship between number of new slices made by $n^{th}$ cut w.r.t to existing number of slices is as follows, and quite convincing:

"And after some thought we realize the appropriate generalization. The $n^{th}$ line (for $n > 0$) increases the number of regions by $k$ if and only if it splits $k$ of the old regions, and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different  places. Two lines can intersect in at most one point. Therefore the new line can intersect the $n-1$ old lines in at most $n-1$ different points, and we must have $k \le n$."

After a couple of reads, i 'seemed to understand' this paragraph and started solving the problem with the recurrence $S_n=S_{n-1}+n$ where $S_n$ is number of slices after $n^{th}$ cut and $S_{n-1}$ is number of slices after $n-1^{th}$ cut.
Then reached to the conclusion fairly easily without reading further text that $S_n = 1 + n(n+1)/2$

However, reality about the 'seemed to understand' part of it stuck right in my face or should i say under my skull when i started to solve an extension to this problem given out as an exercise in the book.

The extension kind of asks you to find the number of slices without the round edges after $n^{th}$ cut, or simply the tastier slices 😃

If i really understood "and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different  places.", i  would not have scribbled away 3 A4 sheets trying to understand how a new cut is changing the existing slices.

So, i would go on to claim here that you have not read a technical book until you solved all the exercises. And also do not look at the solution until you have one. Look at the solution only for comparison. If you cannot solve the problem, either try longer if you can afford the time, or skip it and come back to it on another day or another time of that day, but never look at the solution. Curiosity kills of course.

Well now i explain in my own terms as how each $n^{th}$ cut changes the slices:

Lets start with a pizza already sliced out by 4 cuts as below (this time around cuts are labelled 1,2,3 and 4 instead of the slices)

Lets see what happens now if we make a $5^{th}$ cut across these 4 existing cuts

So our $5^{th}$ cut is entering from the left and cuts the rounded slice into two as it touches cut #1.

As our $5^{th}$ cut passes through cut #1 and touches cut #2, it splits the slice bound by cuts 1 and 2. Here we have one slice with a round edge on the top, and one below which is all cheese.

So, it goes on as the $5^{th}$ cut passes through cuts 2, 3, and then on to cut 4.
As we can see, when a cut passes through 2 existing cuts, it creates exactly one new slice without rounded edge.

Finally, as the cut crosses cut #4 and meets the edge of the pizza it splits that right most slice into two.


Looking at all of this, we can now say that every cut creates 1 rounded slice on its way in, and 1 rounded slice on its way out for sure.
And as it runs its course along the pizza, it creates as many slices without rounded edge as the distinct pairs of existing cuts it goes across.

Visually, we can easily see that if there already are $n-1$ cuts, then the $n^{th}$ cut creates $(n-1)-1 = n-2$ full cheese slices (i.e., ones without the round edge).


Putting this together

$S_n = S_{n-1} + 2 + (n - 2) = S_{n-1} + n$

But would this recurrence hold for $n=1$ as there are no existing cuts?
It would, because the first cut just goes across the pizza end to end, and divides it into two slices.

Now that "and it splits $k$ old regions if and only if it hits the previous lines in $k-1$ different  places." is established properly in the brain, it is quite easy to calculate the number of all cheese slices

$C_n = C_{n-1} + (n-2) = n-2 + n-3 + ... + C_3 = n-2 + n-3 + ... + 1 = (n-2)(n-1)/2$

Lastly, after experiencing this volatility in the brain where you sometimes seem to understand a concept, and sometimes do not. And also you sometimes have solved a problem in past which you cannot now, i was thinking of ways to overcome it.. And the only way i can think of is, start from scratch always.

The only consolation out of this misery that comes to me is a piece of information i read about this great mathematician called Jakob Steiner who apparently presented a solution to this problem, or should we say made this problem popular in 1800 something...
https://en.wikipedia.org/wiki/Jakob_Steiner
" He never prepares his lectures beforehand. He thus often stumbles or fails to prove what he wishes at the moment, and at every such failure he is sure to make some characteristic remark."

When simple gets complex

As i was topic hopping on a lazy day, i stumbled upon this seemingly simple exercise (3.1-2) from chapter 3 of "Introduction to Algorithms" -CLRS

What makes me write about this is the actual amount of time i spent, trying to formally prove it to myself :-)

And of course, after having my rather long proof, i thought there must be a much more elegant one.

Well, before reading further, i recommend you to try the proof yourself or recollect it if done already, for there is a good chance yours is that 'everyone can understand in 2 simple steps' kind of a proof 👍

What you need to prove is that there exist positive constants $c_1$, $c_2$, and $n_0$ such that:

\(c_1 * n^b \leq (n+a)^b \leq c_2 * n^b\)      \(\forall{n} > n_0 \) where $a,b \in \mathbb{R}$ and b > 0

Which is tersely represented as " \( (n+a)^b = \Theta (n^b) \)" in algorithm analysis literature

  _______
 /  12   \
 |    |    |
 |9   |   3|
 |     \   |
 |         |
 \___6___/

Enough time has passed, and i guess you have your proof ready. Be ready to have some fun now looking at what follows as a proof below 😛

Part I -- $\Omega$

Lets begin by the assumption $c * n^b \le (n+a)^b$ where '$c$' is not really a constant, but a suitable variable for each possible $n$.

                => $c \le ((n+a)/n)^b$

If $a \gt 0$, $c_1=1$ readily makes $n^b < (n+a)^b$

But, if $a \lt 0$, such that $|a|=d$, then we have $c*n^b \le (n-d)^b$:

=> $c \le ((n-d)/n)^b$

for $c $ to be $\gt 0$, $n$ has to be greater than $d$, and we have:

 $c \in  \{ 1/(d+1)^b, $

             $(2/(d+2))^b,$

             $(3/(d+3))^b,$

             $ .. $

        $ \}$

 $\forall{n} \in \{d+1, d+2, d+3, .... \}$

If $c$ is an ascending series, we can safely take the lowest value in the progression for the constant.
If $c$ is a descending series, then as you may have guessed, we would never be able to find a $c_1 \in c$ small enough to make the (in)equation $c_1*n^b \le (n+a)^b$ hold for arbitrarily large $n$.
Note that there can be other functions which are not purely ascending or descending, but luckily the one we are dealing with right now is. Why? Because in our $i{th}$ term $(i/(i+d))^b$ there is no component which can change sign as $i$ increases from $1$ to any arbitrarily large value.

So lets spell out the $i^{th}$ and $i+1^{th}$ term of $c$
$c_i = (i/(i+d))^b$ and $c_{i+1} = ((i+1)/(i+1+d))^b$

If we ignore the exponent and look at the difference in base values of $i^{th}$ and $i+1^{th}$ element, we have

$\Delta_{i,i+1} = (i+1)/(i+1+d) - i/(i+d)$

 $= ((i+1)(i+d) - i(i+1+d))/(i+d)(i+1+d)$

Ignoring the denominator, we have the numerator as:
$ \require{cancel} \cancel{i^2 + {i*d} + i} + d - \cancel{(i^2 + {i*d} + i)} = d$ which is positive.
Hence $1/(d+1)^b$ is going to be less than other terms.
And thus if we choose $c_1$ as $1/(|a|+1)^b$, we have $c_1*n^b \le (n+a)^b$ $\forall n \gt |a|$

So, $(n+a)^b = \Omega(n^b)$

Part II -- Big-Oh 
 Now lets consider
$(n+a)^b \le c_2 * n^b$  => $c_2*n^b \gt (n+a)^b$ => $c2 \ge ((n+a)/n)^b$

When $a \lt 0$, the fraction $(n+a)/n$ would be less than one and hence $c_2 = 1$ would suffice.
But, when $a \gt 0$, the fraction $(n+a)/n > 2$ $\forall{n} < a$, and $(n+a)/n < 2$ $\forall{n} > a$
The above observation is intuitive, and also not too difficult to prove formally.
If n < a, $a$ can be expressed as $a = n + x$ where $x \gt 0$.
     => $(n+a)/n =$
                     $(n+n+x)/n = 2n/n + x/n =$
                             $2 + x/n$
Since x/n is positive, we have $(n+a)/n > 2$
If n > a, then $n$ can be expressed as $n = a + x$ where $x \gt 0$.
     => $(n+a)/n =$
                     $(a+a+x)/(a+x) = $
                             $a/(a+x) + 1$
Since $a/(a+x)$ will always be less than 1, we have $(n+a)/n < 2$

Hence for $c_2 = 2^b$ and $n0  = |a| + 1$ we have $(n+a)^b < c2 * n^b$

=> $(n+a)^b = O(n^b)$

Part III -- $\Theta$
from I and II we have:

 $(n+a)^b = \Theta(n^b)$ with $c_1 = (1/(|a|+1))^b; c_2 = 2^b;n_0=|a|+1$

Refinement
in Part II the value we chose for $n_0$ made it such that the constant $a$ was not part of the equation for constant $c_2$.
Can we do something similar for Part I as well? Ofcourse, yes! We had $c \le ((n-d)/n)^b)$ where $d=|a|$
Why not make $n_0 = 2*d$, then we have $c \le (1/2)^b$
Plus from Part I's generic analysis we know that $((n-d)/n)^b$ is an increasing series of numbers.
So, the simpler choices would then be $n_0 = 2 * |a|$ and $c_1 = (1/2)^b$

However, we still have some constants from the earlier inelegant Part-I that can be helpful if $a$ is a pretty big negative number 😉

Summary
As an after thought i don't regret this proof so much but understand the importance of elegance and simplification even more better than before. Hope you did so too 😃
Now try to prove the way you have been mutliplying multi-digit numbers since primary school is actually correct.