Self-containing trees

Question

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining tree. Does every complete subtree of $T(r)$ properly contain itself? More generally, for what choices of $r$ does $T(r)$ properly contain itself?

Some background:

For $r^2-r-1=0$, the first 4 generations of $T(r)$ are $$(1), (r,2), (r+1,2r,3), (2r+1,r+2,2r+2,3r,4).$$

For every node $x$ of $T(r)$, let $T_x$ be the complete subtree with root $x$. It appears that $T_2 = T_1$; i.e., the trees are identical (but with different labelings), so that $T_1$ properly contains itself. The main question can be refined: for each $x$, what is the least $y > x$ such that $T_x$ properly contains $T_y$ (assuming that there is such a $y$)? Here, "least" refers to the order in which nodes appear in the construction of $T(r)$.

Answer 1

This is not an answer, but it's too long for a comment. Let me rewrite the rule for generating the tree in a more algorithmic fashion. Instead of the element $a_0 + a_1 r$ (of the ring of integers $\mathbb{Z}[r]$ of $\mathbb{Q}(\sqrt{5})$), I'll just write $(a_0,a_1)$, where $a_0,a_1 \in \mathbb{Z}$. The algorithm is then as follows:

• Start by creating the node $(1,0)$ as root, and add it to a queue.

• Repeatedly: remove the node $(a_0,a_1)$ from the start of the queue, create the node $(a_1,a_0+a_1)$ and then the node $(a_0+1,a_1)$, if they have not already been created, as its children, and add them to the queue (in that order, at the end).

We get something like this (writing nx_y for $(x,y)$, i.e., $x + ry$):

If someone wishes to reproduce, the Perl code is as follows:

#! /usr/local/bin/perl -w

use strict;
use warnings;

my @queue = ([1,0,0]);
my %hash;

print "digraph kimberling {\n";

while (1) {
    my $r = shift @queue;
    my $v0 = $r->[0];
    my $v1 = $r->[1];
    my $vg = $r->[2];  # Generation
    last if $vg > 5;
    my $vn = "${v0}_${v1}";
    $hash{$vn} = 1;
    my $l0 = $v1;
    my $l1 = $v0+$v1;
    my $lg = $vg+1;
    my $ln = "${l0}_${l1}";
    if ( ! $hash{$ln} ) {
        push @queue, [$l0,$l1,$lg];
        print "    n$vn -> n$ln;\n";
        $hash{$ln} = 1;
    }
    my $r0 = $v0+1;
    my $r1 = $v1;
    my $rg = $vg+1;
    my $rn = "${r0}_${r1}";
    if ( ! $hash{$rn} ) {
        push @queue, [$r0,$r1,$rg];
        print "    n$vn -> n$rn;\n";
        $hash{$rn} = 1;
    }
}

print "}\n";

(save the output to a .dot file and use Graphviz to produce the image).

This graph makes me unhappy for two reasons. One is that there is a childless node ($(1,4)$). The other is that the number of nodes in each level is not, as I had expected, given by the Fibonacci numbers. But searching the first few terms in the OEIS, I see that you got there first. The sequence giving the number of children of each node in breadth order (2, 1,2, 2,1,2, 1,2,2,1,2, 1,1,2,1,2,2,1,2, 2,1,0,2,2,1,2,1,2,2,1,2…) does not appear remarkable either.

Since the question is a form of "base $r$ representation" of the elements of $\mathbb{Z}[r]$, I'll ask Jacques Sakarovitch what he thinks about it next time I see him.