Proof by induction for a recursive function

Question

Really having a tough time doing this 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 each of the following properties holds for f by using induction on $n \in \Bbb N$:

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

Answer 1

HINT

For 1) :

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

ii) induction step : assume that $f(n) = (2 \times n) + (2 \times n)$ and compute $f(n+1)$.

By the recursive definition of $f$, we have ; $f(n+1) = f(n) +4$; substituting for $f(n)$ the formula of the induction hypothesis, we have :

$$f(n+1) = f(n) +4 = (2 \times n) + (2 \times n) +4 = [(2 \times n) +2] + [(2 \times n)+2] = (2 \times (n+1)) + (2 \times (n+1)).$$

---

For 2) :

again the base case $f(0)$ is trivial.

Assume now that $f(n+n)=f(n)+f(n)$ and compute $f((n+1)+(n+1))$ :

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

by the previous result.

But by : $f(n+1)=f(n)+4$ (by recursive definition of $f$) and $f(n)=4n$ (by previous result), we have that : $f(n+1) = 4n+4$.

Thus, substituting, we get :

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