# 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.

• Avoid the use of $*$ to denote multiplication. That's a common practice in programming, not in Mathematics. Use a \times b to get $a\times b$, a \cdot b to get $a \cdot b$ or simply use juxtaposition. May 24 at 0:33

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

1. the lines from points of $$A$$ to points of $$A$$ ($$f(a)$$),
2. the lines from points of $$B$$ to points of $$B$$ ($$f(b)$$),
3. the lines from points of $$A$$ to points of $$B$$ ($$ab$$).

Clearly it does not matter how $$A$$ and $$B$$ are chosen.

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.

• Isn't this only proving that the condition/statement is true, if $b = 1$ is chosen at each step of the recursion? May 23 at 12:48
• No, the last line is check that the condition is satisfied for any $b$. Case $b = 1$ was used only to find the function (to simplify the check). Sometimes it's a useful method to check if some conditions are compatible: take some of them so it's easy to find an object that satisfies them, and then check that this object satisfies the rest too. May 23 at 13:02
• Ok, thank you I think I understand it now, why it also proves this for any $b$. May 23 at 13:04

Basically, you are trying to answer two questions here:

1. 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.
2. 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}^+$$.