Proving a recursive formula is indeed a function 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.
 A: 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

*

*the lines from points of $A$ to points of $A$ ($f(a)$),

*the lines from points of $B$ to points of $B$ ($f(b)$),

*the lines from points of $A$ to points of $B$ ($ab$).

Clearly it does not matter how $A$ and $B$ are chosen.
A: I think it's simpler to find what explicit formula for $f$ can be, and then check that it satisfies the equation.
The simplest way to find it is to substitute $b = 1$ and get $f(n) = f(n - 1) + n - 1$. Substituting it into itself we get $$f(n) =\\ f(n - 1) + (n - 1) =\\ f(n  - 2) + (n - 2) + (n - 1) =\\ \ldots =\\ (n - 1) + (n - 2) + \ldots = \frac{n(n - 1)}{2}$$
Now, we can check that it indeed satisfies the condition: $$f(a + b) = \frac{(a + b)(a + b - 1)}{2} = \frac{a(a - 1)}{2} + \frac{b(b-1)}{2} + ab = f(a) + f(b) + ab$$
So, if there is a function satisfying the conditions, then it is $f(n) = \frac{n(n - 1)}{2}$. And this function satisfies the conditions. So the conditions define this function.
A: Basically, you are trying to answer two questions here:

*

*Does there exist a function $f : \mathbb{N}^+ \to \mathbb{N}$ satisfying the properties below? If there is no such function, obviously you can not use these properties as a definition.

*Does there exist a unique function satisfying the properties below? If there are multiple such functions, then again you can not use these properties as a definition.

\begin{equation}
f(1) = 0 \quad \text{and} \quad \forall a, b \in \mathbb{N}^+ \ f(a + b) = f(a) + f(b) + ab 
\end{equation}
Existence is pretty clear. In the mihaild's answer, it is proved that the function $f(n) = \frac{n (n - 1)}{2}$ works.
For uniqueness, assume that functions $f$ and $g$ satisfy our properties. Using induction, we will show that $f(n) = g(n)$ for all $n \in \mathbb{N}^+$.
i. First step of the induction is trivial. By assumption, we have $f(1) = g(1) = 0$.
ii. Let $n > 1$. For the induction hypothesis, assume $f(n-1) = g(n-1)$. By assumption, we have:
\begin{align}
f(n) &= f(1 + n-1) = f(1) + f(n - 1) + n - 1 = f(n - 1) + n - 1 \\
g(n) &= g(1 + n-1) = g(1) + g(n - 1) + n - 1 = g(n - 1) + n - 1
\end{align}
But from our induction hypothesis $f(n - 1) = g(n - 1)$ therefore $f(n) = g(n)$. This closes the induction and we conclude that $f(n) = g(n)$ for all $n \in \mathbb{N}^+$.
