Here is the problem:
Consider the set $S \subseteq \Bbb{N}^2$ defined recursively by the following rules:
- $(3, 2) ∈ S$;
- if $(x, y) ∈ S$, then $(3x − 2y, x) ∈ S$.
Let $R$ = {($2^{k+1} + 1$, $2^k + 1$) $\mid k ∈ \Bbb N\}$. Use simple or complete induction to prove that $R \subseteq S$.
I think my $P(n)$ is wrong. I specified $P(n)$, that is $R\subseteq S$. For IH, I said let $(x,y) \in S$. Assume $P(x, y)$ holds.
For the inductive step, I want to prove $P(x + 1, y + 1)$, so I do that and plug it into $(3x − 2y, x)$, getting $(3(x + 1) − 2(y + 1), x + 1)$. That simplifies to $(3x - 2y + 1, x + 1)\in S$.
Now how would I use the IH to prove $P(x + 1, y + 1)$?
We will prove using induction that
$$(\forall k\ge 0)\;\;(2^{k+1}+1,2^k+1)\in S$$
For $k=0$, we check easily that $$(2^{k+1}+1,2^k+1)=(3,2)\in S$$
Let $k\ge 0$ such that $$(2^{k+1}+1,2^k+1)\in S$$ (Induction Hypothesis) and let us prove that $$(2^{k+2}+1,2^{k+1}+1)\in S.$$
By definition of the set $ S,$
$$(2^{k+1}+1,2^k+1)\in S \implies$$ $$3(2^{k+1}+1)-2(2^k+1),2^{k+1}+1)\in S \implies$$ $$(3-1)2^{k+1}+3-2,2^{k+1}+1)\in S \implies$$ $$(2^{k+2}+1,2^{k+1}+1)\in S$$ Done.