Let $f: N -> N$ be a fucntion satisfying $f(n+m) = f(n) + f(m)$ for all $m$ and $n$. Prove that there exist a constant $c$ so that $f(n) = cn$.

Question

The question is actually Example 2.6 from A walk through combinatorics. The solution given below is exactly as in book.

Let $m = 0$, then $f(n + 0) = f(n) + f(0)$, so $f(0) = 0$, and the base case is complete. Now let us assume that we know the statement is true for all natural numbers less than or equal to $n$. That is, there exists a constant $c$ so that $f(k) = ck$ if $k \leq n$. In particular, that means $f(1) = c$ and $f(n) = cn$. This implies that $f(n+1) = f(n) + f(1) = cn + c = c(n+1)$, and the statement is proved.

Is the proof correct? I mean in induction it uses the fact that $f(1) = c$ which is not proven in the base step. And even if we try to prove it the similar way as we are doing in induction step for $f(n+1)$, we will get $f(1 + 0) = f(0) + f(1)$, thus $f(1) = f(1)$ not $f(1) = c$ which we want.

Answer 1

$f(1)$ has to equal something, Call it $c$.

Answer 2

If that induction step is difficult to understand, you can do it directly and see why $f(1) = c$ (it's not a given constant, it's what you'll have to show):

$$f(n) = f(n-1 + 1) = f(n-1) + f(1) = f(n-2)+f(1)+f(1) = \cdots = nf(1)$$

so that constant is indeed $f(1)$.