Let $S$ be the set of polynomials defined as follows: $0$ is in $S$, and if $p$ is in $S$, then $p + 1$ is in $S$ and $x \cdot p$ is in $S$, so that $S$ "grows" in generations: $g(0)=\{0\}$, $g(1)=\{1\}$, $g(2)=\{2,x\}$, $g(3)=\{3,2x,x+1,x^2\}$, and so on, with $|g(n)|=2^{n-1}$. Let $S^\*$ be the set obtained from $S$ by substituting $r=\sqrt{2}$ for $x$ and keeping only the first appearance of each duplicate. Successive generations $G(n)$ now begin with $\{0\}$, $\{1\}$, $\{2,r\}$, $\{3,2r,r+1\}$, with $|G(n)|$ starting with $1,1,2,3,4,7,11,18,29,...$; i.e., Lucas numbers beginning at the 4th term, and checked for 30 generations. Can someone prove that $|G(n)|=L(n-1)$ for $n \geq 4$? 



A possibly surprising appearance of Lucas numbers
For a number of the form $a + b\sqrt{2}$ with nonnegative integers $a$ and $b$, define its *length* to be the minimal number of steps needed to obtain it from zero, where the allowed steps are $x \mapsto x+1$ and $x \mapsto \sqrt{2}x$.
Then the problem asks to count the numbers of given length.


Now it should be easy to show the following by induction:


* If $a$ is odd, then the last step must be $x \mapsto x+1$ (this is clear).
* If $a$ is even, then the last step can be taken to be $x \mapsto \sqrt{2}x$,
*unless* $a + b\sqrt{2} = 2$.


EDIT: Here is a proof. Let $\ell(x)$ be the length of $x$.



> 
> **Lemma.** Write $x = a\_0 + a\_1 \sqrt{2} + a\_2 \sqrt{2}^2 + \ldots + a\_k \sqrt{2}^k$
>  with $a\_j \in \{0,1\}$ and $a\_k = 1$.
> 
> 
> If $x > \sqrt{2}$,
>  then $\ell(x) = k + \#\{j : a\_j = 1\} - (1 - a\_{k-1})$.
> 
> 
> 


*Proof.* Write $\ell'(x) = k + \#\{j : a\_j = 1\} - (1 - a\_{k-1})$.
The proof is by induction on $x$ (the set of all possible $x$ has the
order type of the natural numbers).
We have $\ell(1 + \sqrt{2}) = 3 = \ell'(1 + \sqrt{2})$.
So assume $x \ge 2$.
If $a\_0 = 1$, then $\ell(x) = \ell(x-1) + 1 = \ell'(x-1) + 1 = \ell'(x)$
(this needs that $0 \neq k-1$, so that changing $a\_0$ from
1 to 0 does not affect $a\_{k-1}$).
If $a\_0 = 0$, then
$\ell(x) \le \ell(x/\sqrt{2}) + 1 = \ell'(x/\sqrt{2}) + 1 = \ell'(x)$,
so we need to show
that $\ell'(x-1) \ge \ell(x/\sqrt{2}) = \ell'(x) - 1$.
We can assume $x > 2$, since
the claim of the lemma holds for $x = 2$. The rational part (denoted $a$
above) of $x$ must be at least 2 (it must be positive, otherwise $x-1$
is not of the required form, and even since $a\_0 = 0$). Then in $x-1$,
either $k$ stays the same and we have the same or a larger number of 1's
among the $a\_j$, which shows
$\ell'(x-1) \ge \ell'(x) - 1$. (Note that $a\_{k-1}$ could change from 1 to 0.)
Or else $k$ gets smaller; then $a = 2^m$ and $k = 2m$ in $x$, and
$a = 2^m-1$, $k \le 2m-1$ in $x-1$. So we reduce $k$ by at least 1, but increase
the number of 1's by $m-1$. Note also that $a\_{k-1}$ can only change
from 1 to 0 if $k$ goes down by 2. So
$\ell'(x-1) \ge \ell'(x) + m - 2 \ge \ell'(x) - 1$ as before. $\Box$


Assuming this, we can arrange our numbers $a + b\sqrt{2}$ into a rooted tree
with zero at the root and where an odd number (meaning odd $a$) has only one
(even) child, whereas an even number has two children, one odd and one even.
There are two exceptions: the odd node $1$ has the two children $2$ and $\sqrt{2}$,
and the even node $\sqrt{2}$ has only one child $1 + \sqrt{2}$.
So the $n$th level of the tree, for $n \ge 3$, consists of the $n$th level
of the usual Fibonacci tree (think of the rabbits) (with root $1$), together
with the ($n-2$)nd level of the Fibonacci tree (with root $1 + \sqrt{2}$).
This gives $F\_n + F\_{n-2} = L\_{n-1}$ for the number of nodes at distance $n$
from the root (the root has level $1$).


REMARK. Replacing $\sqrt{2}$ by $2$ gives a somewhat simpler problem that
leads to the Fibonacci tree (starting at $1$) and gives Fibonacci numbers.
The golden ratio $(1+\sqrt{5})/2$ gives the sequence $(1,2,3,5,8, 12, 18, 25, 35, 51,\ldots)$
(starting at generation 1), apparently satisfying
$a\_n = a\_{n-1}+a\_{n-3}$ for $n \ge 12$.
[Previously, I claimed that one gets Fibonacci numbers, but this is wrong.]
If we take any number $r > 1$ instead of $\sqrt{2}$, then I would expect
that for any $x \in R = {\mathbb Z}\_{\ge 0}[r]$ that is divisible by $r$
and sufficiently large, the shortest path to zero is via division by $r$.
For any other $x$, one is forced to go via $x-1$. So in the relevant tree,
if we are at a sufficiently high level, nodes $x$ such that $x+1$ is
divisible by $r$ in the semiring $R$ have one child $rx$ and the other
nodes have two children $x+1$ and $rx$. I would expect this to lead to
a linear recurrence with constant coefficients, but since we are dealing
with a semiring and not with a ring (where we could consider the quotient
by the ideal generated by $r$), this is not clear to me.


