Given a infinite binary tree rooted at node 1 where children of node $i$ are $2i$ and $2i+1$, with each node having a value $v(i)$. The values of the first $k$ nodes are given, the value of any node numbered above $k$, $v(i) = v(i$ mod $k)$.
From these basic initial conditions, I ask the open-ended question of what would be some examples of interesting recurrences which:
(1) output a specific value at the root (ie. not an infinite)
(2) this final value can be calculated in polynomial time (ie. there is a way to simplify the infinite recurrence so it does not take infinite time to calculate, and it does not take an impractically long time to calculate either)
I have worked on this for many hours now, but I am unfortunately not very experienced in this field and so have not found some good examples of recurrences. However, I have (I believe) found a pattern to the tree that I describe below (though I have not yet found any utility to this pattern). Any comments on interesting recurrences (preferably with solutions) or on additional properties of this binary tree which may help me find recurrences would be appreciated!
So far, my results are that I have found a pattern in the position of all nodes numbered a (mod k) in the binary tree. The lowest numbered node on a layer that has a value of a (mod k) cycles. To illustrate what I mean, take the example of a tree where k=3. If we are considering nodes which are numbered 1 (mod k), the nodes are 1,4,7,10,13,etc. The node numbered 4 is the first node on layer 3. The node numbered 7 is the third node on layer 4. The node numbered 13 is the first node on layer 5. So, we see a pattern where the first node on each layer which is numbered 1 (mod k) is 1,3,1 etc. If the binary tree is constructed further, we can see this pattern holds. It also holds for other values of a.
We can divide the binary tree into two sections: the section before this cycle starts and the section from there on where the cycle continues infinitely. In the above case, the section before the cycle starts would be the first 2 layers.
This cyclic behaviour should always hold (I have a semi-proof which I can post in comments), however if it does not I would also appreciate comments saying that and giving a reason why.
Apart from this, I have looked into probabilities as a possibility for avoiding infinite values from being output, however I have not looked much further on that issue.
Thanks for any and all help!