Proving a recursive formula is indeed a function

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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