Proof by induction for a recursive function f

Question

Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows:

1) Base case: $\operatorname{f}(0) = 0$

2) Recursive case: $\operatorname{f}(x) = \operatorname{f}(x-1)+4$, for any $x>0$

Prove that the following property holds for f by using induction on $n \in \Bbb N$:

$$2) \operatorname{f}(n+n)=f(n) + f(n)$$

This is what I have so far:

Base case : $f(0) = 0 = (2 \times 0) + (2 \times 0)$

Induction step :

Assume that $f(n + n) = f(n) + f(n)$

Show that $f((n+1)+(n+1))$ = $f(n+1))$ + $f(n+1))$

$$f((n+1)+(n+1)) = f((n+1) + n) + 4$$

Now I'm stuck and don't have a clue what to do next!

Answer 1

You are almost there. Just apply the recursion again: $$\begin{align}\\ f(n+1+n+1) &=f(n+1+n)+4\\ &=f(n+n+1)+4\\ &=f(n+n)+4+4\\ &=f(n+n)+8\\ &=\{\text{induction hypothesis}\}\\ &=f(n)+f(n)+8\\ &=f(n)+4+f(n)+4 \end{align}$$

Now, what can you do with that last expression?