Consider the following recursive definitions of two functions from $\mathbb N \to \mathbb N$
$$ F(n) = \begin{cases} 1 & n = 0 \\ 2 & n = 1 \\ F(n-2)^2 \cdot F(n-1) & n > 1 \end{cases} $$
$$ G(n) = \begin{cases} 1 & n = 0 \\ 2G(n-1)^2 & n > 0 \text{ and n is odd } \\ G(n-1)^2/2 & n > 0 \text{ and n is even } \end{cases} $$
Use induction to prove $F(n) = G(n)$ for all $n \in \mathbb N$
ANSWER: \
Basis:
For $n = 0$,
$F(0) = 1 = G(0)$ [By definition of G and F].
Therefore $F(n) = G(n)$ as wanted
For $n = 1$,
$F(1) = 2$ [By definition of F]
$= 2(1)^2$ [manipulated numbers]
$= 2G(0)^2$ [By definition of G(0)]
$= 2G(1-1)^2$ [manipulated numbers]
$= G(1)$ [definition of G when n is odd]
Therefore $F(n) = G(n)$ as wanted
Ind step: Let $n \geq 2$. Suppose $F(j) = G(j)$ whenever $0 \leq j < n$ [I.H]
WTP: $F(n) = G(n)$
Two cases: When n is even and odd
let n be an odd number:
$F(n) = F(n-2)^2 \cdot F(n-1)$ [Definition of F; $n > 1$]
$= G(n-2)^2 \cdot G(n-1)$ [I.H]
$= 2G(n-1) \cdot G(n-1)$ [Definition of G; $n > 0$ and even]
$= 2G(n-1)^2$
$= G(n)$ [Definition of G; $n > 0$ and odd], holds
let n be an even number
$F(n) = F(n-2)^2 \cdot F(n-1)$ [Definition of F; $n > 1$]
$= G(n-2)^2 \cdot G(n-1)$ [I.H]
$= \frac{G(n-1)}{2} \cdot G(n-1)$ [Definition of G; $n > 0$ and odd]
$= G(n-1)^2/2$
$= G(n)$ [Definition of G; $n > 0$ and even], holds
therefore $F(n) = G(n)$ as wanted
Would this proof be correct?