Relating graph theory and recurrence relations

Question

I have this assignment problem and its solution.

Question:

Suppose you are given a pile of $n$ stones. At each step, you are allowed to separate a pile of $k$ stones into two piles of $k_{1}$ and $k_{2}$ stones. Obviously, $k_{1} + k_{2} = k$. On doing this, you earn $k_{1} * k_{2}$ dollars. What is the maximum amount of money you can earn starting with a pile of $n$ stones? Explain your answer.

Suggested solution(Using graph theory):

One can earn at most $\frac{n(n – 1)}{2}$ dollars.

1. Represent each stone as a vertex in a complete graph $K_{n}$.
2. Two vertices representing two stones are connected if the stones are in the same pile.
3. In the beginning, every stone is in the same pile as every other stone, so there are $\frac{n(n – 1)}{2}$ edges in the graph.
4. Separating a pile of $k$ stones into two piles of $k_{1}$ and $k_{2}$ stones corresponds to removing some edges from the graph. The number of edges removed is exactly $k_{1} * k_{2}$.
5. The maximum amount of money one can earn is when the stones are separated into piles with single stone, that is, when all the edges are removed.
6. Since the number of edges in $K_{n}$ is $\frac{n(n – 1)}{2}$, this is the maximum amount one can earn.

As I was still quite new to graph theory(and its subsequent combinatorial thinking), I thought of it as a calculus problem instead, and tried writing a suitable recurrence relation. As a calculus problem, the way we split the pile would matter,splitting up the pile as equally as possible in each recursive step should yield the greatest product hence the greatest amount of money in my opinion, not sure if the graph theory solution, which shows the final outcome instead of the process, has accounted for the sequence of splitting.

The recurrence for $f(n)$, which will get us the maximum amount of money, consists of 2 parts:

For an even number $n$ which is expressed as $2k$:$$f(2k)=k^{2}+f(k)+f(k)$$

For an odd number $n$ which is expressed as $2k+1$: $$f(2k+1)=k(k+1)+f(k)+f(k+1)$$

Combining the 2 results to recreate $f(n)$ in terms of $n$: $$f(n)=\lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil +f(\lfloor \frac{n}{2} \rfloor)+f(\lceil \frac{n}{2} \rceil)$$

Theoretically, since the suggested answer to this question is $\frac{n(n – 1)}{2}$, I am interested to know whether it is possible to deduce the final closed form expression for this recurrence. This means to say that it is possible to solve this new problem:

Given the recurrence $$f(n)=\lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil +f(\lfloor \frac{n}{2} \rfloor)+f(\lceil \frac{n}{2} \rceil)$$, subject to

$$f(0)=0, f(1)=0$$, show that $$f(n)=\frac{n(n – 1)}{2}$$.

However, I do not know many numerical properties that relate to floor and ceiling functions because I'm not a Mathematics Major, and most of them that I have found online either relate to some series or some inequality, neither of which actually allows me to prove a precise equality statement. May I know if my initial intuition about the problem is right? If it is indeed right, is it actually possible to deduce that the closed form expression of this recurrence to be the suggested answer?

Answer 1

Given the recurrence $$f(n)=\left\lfloor \frac{n}{2} \right\rfloor \left\lceil \frac{n}{2} \right\rceil +f\left(\left\lfloor \frac{n}{2} \right\rfloor\right)+f\left(\left\lceil \frac{n}{2} \right\rceil\right)$$ subject to $$f(0)=0, f(1)=0$$show that $$f(n)=\frac{n(n – 1)}{2}$$

Proof by strong induction: suppose $f(i) = \frac12 i(i-1)$ for all $0 \le i < n$, and that $n \ge 2$ (so that $\left\lceil \frac{n}{2} \right\rceil < n$). Then if $n$ is even we have $$f(n) = \frac{n^2}{4} + 2f\left(\frac{n}{2}\right) = \frac{n^2}{4} + \frac{n(n-2)}{4} = \frac{n(n-1)}{2}$$ and if $n$ is odd we have $$\begin{eqnarray} f(n) &=& \frac{(n-1)}{2} \frac{(n+1)}{2} + f\left(\frac{n-1}{2}\right) + f\left(\frac{n+1}{2}\right) \\ &=& \frac{(n-1)(n+1)}{4} + \frac{1}{2} \frac{(n-1)}{2} \frac{(n-3)}{2} + \frac{1}{2} \frac{(n+1)}{2} \frac{(n-1)}{2} \\ &=& \frac{n-1}{2} \left(\frac{2n+2}{4} + \frac{n-3}{4} + \frac{n+1}{4} \right) \\ &=& \frac{n(n-1)}{2} \end{eqnarray}$$

---

Note, however, that this doesn't prove that $\frac{n(n-1)}{2}$ is the solution to the original problem, because although my intuition agrees with yours that

splitting up the pile as equally as possible in each recursive step should yield the greatest product hence the greatest amount of money in my opinion

that needs proof. Again, we can use strong induction. Suppose again that $f(i) = \frac12 i(i-1)$ for all $0 \le i < n$, and that $n \ge 2$. Then $$\begin{eqnarray}f(n) &=& \max_k k(n-k) + f(k) + f(n-k) \\ &=& \max_k k(n-k) + \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2} \\ &=& \max_k \frac{2k(n-k) + k(k-1) + (n-k)(n-k-1)}{2} \\ &=& \max_k \frac{n^2 - n}{2} \\ &=& \frac{n^2 - n}{2} \end{eqnarray}$$