Recently, I have been studying induction proofs, because I wanted to learn about all kinds of different proof techniques. However, I have been stuck now on this particular exercise for a while now.
Let $f$ be defined for $n \geq 1$ as follows
\begin{equation*}
f(n) =
\begin{cases}
0 & \text{for } n = 1 \\
f(a) + f(b) + ab & \text{for } n > 1, a + b = n, a,b \in \mathbb{N}^+
\end{cases}
\end{equation*}
Prove that $f$ is a function, in particular, prove that for every $n \geq 1$, $f(n)$ will always produce the same value, regardless of how $a, b$ are chosen in each recursive step.
I tried proving this with strong induction. For the base case $n = 1$, its trivial this is true, since by definition $f(1) = 0$ is always the case. Let the induction hypothesis now be, that the statement holds true for all $k \geq 1$ up to some $n – 1 \geq 1$, so $1 \leq k \leq n – 1$. Now we have $f(n) = f(a) + f(b) + ab$, with $a + b = n$. For a number $n$ there are $n – 1$ different ways to express $a + b = n$, where $1 \leq a, b \leq n – 1$. Some of those will of course be the same, i.e. $2 + 4 = 4 + 2 = 6$ and won't affect the recursion. Since $a, b < n$, the induction hypothesis tells us that the statement already holds true for $f(a), f(b)$. My problem now is that I need to show that the following is true
\begin{equation*}
\begin{split}
f(n) &= f(1) + f(n-1) + (n-1) \\
&= f(2) + f(n-2) + 2(n-2) \\
&= \text{ … } \\
&= f(n-2) + f(2) + (n-2)2 \\
&= f(n-1) + f(1) + (n-1) \\
\end{split}
\end{equation*}
Obviously, the first and last, second and second to last and so on are all equal. But for example how do I show that $f(1) + f(n-1) + (n-1) = f(2) + f(n-2) + 2(n-2)$ is true. The induction hypothesis doesn't really help here.
I would really appreciate some help or a hint here.
Best Answer
It's important that you learn how to make a formal argument, as others showed you, but in the case you wonder if there is a simple intuitive argument showing that the choice of $a$ and $b$ in the recursive equation does not matter... here's one.
Draw $n$ points on a board, and connect each of them to all the others with a line. (Don't connect $x$ to $y$ if $y$ was already connected to $x$ -- only one line between them, direction does not matter.) We claim that $f(n)$ is the number of such lines.
Clearly $f(1)=0$ since there are no lines to draw here.
For $n>1$, partition the points into two arbitrary sets $A,B$ of cardinality $0 < a,b < n$ respectively. We therefore have $a+b=n$. Now the recursive case $$ f(n) = f(a)+f(b)+ab $$ reads as: the total number of lines can be obtained by counting
Clearly it does not matter how $A$ and $B$ are chosen.