$f_{n}$ is a sequence of natural numbers defined by a relation:
$f_{0} = 0$
$f_{1} = 1$
$f_{2} = 2$
$f_{n+3} = f_{n} - 2f_{n+2} + 3$
There is also a function $g$ defined by a primitive recursion with a substitution in parameters:
$g(0, a, b, c) = c$
$g(n + 1, a, b, c) = g(n, b, c, a − 2c + 3)$
I have to prove that this is applicable for every natural number $n$:
$f_{n+2} = g(n, 0, 1, 2)$
I have seriously no idea what to do about that. Any hints/ideas? Sorry for bad English, that is not my first language.
Firstly, looking at the problem, it's about natural numbers, right? So the typical technique to try is induction. However, I get stuck. In the inductive step, applying the recursive definition $g(n + 1, a, b, c) = g(n, b, c, a - 2c + 3)$ gives $g(n, 0, 1, 2) = g(1, 2, -1)$ which is leading to nowhere. So let's change our strategy and try to solve a more general problem!
Define $$h(n, a, b, c) = \begin{cases} a \text{ if } n = 0 \\ b \text{ if } n = 1 \\ c \text{ if } n = 2 \\ h(k, a, b, c) - 2 h(k + 2, a, b, c) + 3 \\ \text{ if } n = k + 2 > 2\end{cases}$$ Notice $f_n$ is the same function as $n \mapsto h(n, 0, 1, 2)$, you can think of this as partial application if you know functional programming. Therefore, it suffices to prove $$h(n + 2, a, b, c) = g(n, a, b, c) \ \forall n \in \mathbb{N}, a, b, c \in \mathbb{Z}$$ We will prove this by induction. For the base case, $h(2, a, b, c) = c = g(0, a, b, c)$ by definition. For the inductive step, assume that there's some $n \in \mathbb{N}$ such that $$h(n + 2, a, b, c) = g(n, a, b, c) \ \forall a, b, c \in \mathbb{Z}$$ Now $$\begin{align}g(n + 1, a, b, c) &= g(n, b, c, a - 2c + 3) \\ &= h(n + 2, b, c, a - 2c + 3)\end{align}$$ by definition and inductive hypothesis. Note that to complete the proof, we are only left to show $$h(n + 2, b, c, a - 2c + 3) = h(n + 3, a, b, c) \\ \forall n \in \mathbb{N}, a, b, c \in \mathbb{Z}$$ which can again be shown by induction. I will leave you to check the details. Please ask if you get stuck. So this completes the proof.