6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – jjagmath
    May 24 at 0:33

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Isn't this only proving that the condition/statement is true, if $b = 1$ is chosen at each step of the recursion? $\endgroup$
    – roblox99
    May 23 at 12:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – mihaild
    May 23 at 13:02
  • $\begingroup$ Ok, thank you I think I understand it now, why it also proves this for any $b$. $\endgroup$
    – roblox99
    May 23 at 13:04
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.