# A possibly surprising appearance of Lucas numbers

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$?

• Welcome to MO! I have edited your post to use LaTeX instead of ascii (which was conflicting with MO's markup syntax). But I think something is missing in your definition of $S$, as multiplying $0$ with $x$ only gives back $0$. Maybe it is also allowed to add $1$? – darij grinberg Jan 29 '15 at 17:52
• Responding to D.Z., calling it r suggests the more general problem of using an arbitrary algebraic number (such as the golden ratio). Then the main question is this: Is $G(n)$ linearly recurrent. – Clark Kimberling Jan 29 '15 at 20:35
• I think the main step here is the following observation (for $r = \sqrt 2$): Every element $q$ of $\mathbb{N} + \mathbb{N}r$ can be written uniquely as a finite sum $r^{a_1} + r^{a_2} + ... + r^{a_k}$ for nonnegative integers $a_1,a_2,...,a_k$ satisfying $a_1 < a_2 < ... < a_k$. (Indeed, just write the integral and the $r$-integral parts of $q$ in binary.) We denote the nonnegative integer $k + a_k$ as the energy of $q$ (where $a_k := 0$ if $k = 0$). Now if I am not mistaken, then an inductive argument shows that ... – darij grinberg Jan 29 '15 at 20:42
• ... for every $n \in \mathbb{N}$, every element of $\mathbb{N} + \mathbb{N} r$ having energy $n$ belongs to $G(n)$, and that every element of $G(n)$ must have energy $n$ (these inductions need to happen in lockstep). As a consequence, it easily follows that $G(n)$ is the set of all elements of $\mathbb{N} + \mathbb{N} r$ having energy $n$. – darij grinberg Jan 29 '15 at 20:43
• The induction relies on the lemma that for every $q \in \mathbb{N} + \mathbb{N}r$, the energy of $q+1$ is $\leq$ to (the energy of $q$) plus $1$. This is rather annoying to formalize, but I am fairly sure that the "follow your nose" proof goes through. (The idea is: Write $q$ as $r^{a_1}+r^{a_2}+...+r^{a_k}$ as above. Let $u$ be the smallest even integer which does not belong to $\left\{a_1,a_2,...,a_k\right\}$. Then, $q=r^{b_1}+r^{b_2}+...+r^{b_l}$, where $\left(b_1,b_2,...,b_l\right)$ is the result of removing the entries $0,2,...,u-2$ from the sequence $\left(a_1,a_2,...,a_k\right)$ and ... – darij grinberg Jan 29 '15 at 20:58

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.

• I'm stuck somewhere in the middle of the proof of Michael's Lemma. See where $\ell'(x-1) \ge \ell'(x)-1$? It appears that this is intended to imply $\ell'(x) \le \ell(x)$, so that, with what's proved earlier, we'll have $\ell'(x) = \ell(x)$. However, $\ell'(6-1) = 5 = \ell(5)$. What'm I missing? – Clark Kimberling Aug 24 '15 at 20:48
• Oops. I left something out in the above Comment. Use this one instead. See where $\ell'(x-1) \ge \ell'(x)-1$? It appears that this is intended to imply $\ell'(x) \le \ell(x)$, so that, with what's proved earlier, we'll have $\ell'(x) = \ell(x)$. The desired $\ell'(x) \le \ell(x)$ would follow if $1+\ell'(x-1 \le \ell(x)$, but that's not available; e.g., $\ell'(6-1) = 5 = \ell(5)$. What'm I missing? – Clark Kimberling Aug 24 '15 at 21:08
• $\ell'(6-1) = \ell'(5) = 5 \ge 5 - 1 = \ell'(6) - 1$, so where is the problem? (Also, $\ell(6) = 5 = \ell'(6)$ and $\ell(5) = 5 = \ell'(5)$.) Note that $\ell(x) = 1 + \min\{\ell(x/\sqrt{2}), \ell(x-1)\} = 1 + \min\{\ell'(x/\sqrt{2}), \ell'(x-1)\}$, the second equality by the inductive assumption. If $\ell'(x-1) \ge \ell'(x/\sqrt{2}) = \ell'(x) - 1$, then the first term gives the minimum, and $\ell(x) = \ell'(x)$. – Michael Stoll Aug 25 '15 at 10:39

I seem to be a bit short of a proof. But here is a much refined conjecture which might lead to a proof. I construct sets $H(3),H(4),\cdots$ where $H(n)$ has $L_{n-1}$ elements and then conjecture, with support, that $H(n)=G(n)$ for all $n.$

Just to fix notation, the Fibonacci numbers starting with $F_0$ are $0,1,1,2,3,5,\cdots.$ Call a binary sequence good if it has no two consecutive $0$'s. There are $F_{n+2}$ good binary sequences of length $n$. Of these , $F_{n}$ start with $0$ and $F_{n+1}$ start with $1.$ The Lucas numbers starting with $L_1$ are $1,3,4,7,11,18,\cdots$ with $L_n=F_{n-1}+F_{n+1}=2F_{n-1}+F_n.$

We want to show that, starting with $n=3,$ The set $G(n)$ has size $L_{n-1}.$ I will attempt to do this (but not totally succeed) by associating with each element of $G(n)$ a code consisting of a letter , $A,B$ or $C$, followed by a good binary sequence of length $n-2$, with the added condition that we must start $A0,B0$ or $C1.$ The code will give a unique recipe for each element starting from $H(3)=G(3).$ To be clear I will call the sets I construct $H(3),H(4),\cdots$ and conjecture that they are the same as $G(3),G(4),\cdots$

Here are the cases $n=3,4,5$ with the codes. Skip this example (for now) if you want the recipe first . Read it now if you want to guess the (simple) recipe.

$H(3)=G(3)=\{\sqrt{2}+1,3,2\sqrt{2}\}$ with codes $\{A0,B0,C1\}$

$H(4)=G(4)=\{2+\sqrt{2},3\sqrt{2},2\sqrt{2}+1,4 \}$ with codes $\{A01,B01,C10,C11\}$

$H(5)=G(5)=\{3+\sqrt{2},2+2\sqrt{2},3\sqrt{2}+1,6,4+\sqrt{2},5,4\sqrt{2} \}$ with codes $\{A010,A011,B010,B011,C101,C110,C111\}$

Recipe given $p$ in $H(n)$, put $q=p\sqrt{2}$ into $H(n+1)$ and append $1$ to the end of the the code for $p$ in order to get the code for $q.$ If the code for $p$ ends in a $1$ then also put $q'=p+1$ into $H(n+1)$ and append $0$ to the end of the the code for $p$ in order to get the code for $q'.$

Certainly, if $H(n)=G(n)$ then everything placed in $H(n+1)$ either belongs in $G(n+1)$ or, perhaps, is already in $G(m)$ for some $m \le n.$

CONJECTURE H(n+1)=G(n+1).

I will discuss this a bit more at the end.

Observe that $H(n)$ has $F_{n-2}$ elements whose code starts $A0$, another $F_{n-2}$ which start $B0$ and $F_{n-1}$ whose code starts with $C1.$ In all, this gives

$$2F_{n-2}+F_{n-1}=L_{n-1}$$

elements in $H(n).$

The fact that we never get the same thing twice in building $H(n)$ follows from this observation (an easy induction): Recall that $L_{n-1}=L_{n-3}+L_{n-2}.$

• There are $L_{n-3}$ elements $a+b\sqrt{2} \in H(n)$ with $a$ odd and these are the ones whose code ends in $0.$

• There are $L_{n-2}$ elements $a+b\sqrt{2} \in H(n)$ with $a$ even and these are the ones whose code ends in $1.$

Further Discussion define the weight ( or length) of a number $p=a+b\sqrt{2}$ to be $w(p)=m$ if $p \in G(m).$ Here $a,b \ge 0$ and we will ignore $0,1,\sqrt{2}$ and $2.$ Then for $a=2j+1$ we must have $w(a+b\sqrt{2})=w(2j+b\sqrt{2})+1.$ For $a=2j+2$ we have that $w(a+b\sqrt{2})$ is either $w(b+(j+1)\sqrt{2})+1$ or $w(2j+1+b\sqrt{2})+1$ whichever is smaller. Although this is quite rapid, it is not immediate when $w(p) \lt w(q),$ even for $p,q \in \mathbb{Z}.$

The conjecture amounts to saying that we always have $$w(b+(j+1)\sqrt{2}) \le w(2j+1+b\sqrt{2}).$$ I actually conjecture that this is a strong inequality. For small cases the discrepancy is $1$ or $2.$ However $w(32+8\sqrt{2})=11$ while $w(15+32\sqrt{2})=15.$ For $b=33$ and $b=34$ it turns out that $w(b+8\sqrt{2})=12$ while $w(15+b\sqrt{2})=16.$

For $p=7+11\sqrt{2}$ it turns out that $w(p)=12$, $w(p\pm 1)=w(p\pm \sqrt{2})=11$ and $w(p \pm(1 \pm \sqrt{2})=10.$