4

I can only solve basic linear recurrence relations using characteristic polynomial technique. Then I hit this, and I cannot think of the polynomial that is necessary to solve this problem. If there is any concrete theory behind solving this kind of recurrence relations please provide source to them. Or if this can be solved by following some methods please illustrate how you would approach this kind of problems. The initial terms are $a_1= 1 , a_2 = 1.$

Sami
  • 329
  • Have you tried listing some terms? Declare some initial conditions (not clear to me how many you need) and start from there. Maybe start with $ a_0=1$ and $a_i=0$ for all $i<0$. Something like that (checking that that choice is consistent, of course). – lulu May 26 '19 at 17:58
  • I forgot to mention the initial terms. They are $a_1 = 1, a_2 = 1$. – Sami May 26 '19 at 18:01
  • As I said, starting with some initial conditions, list the first few terms. See if you can spot a potentially useful pattern. – lulu May 26 '19 at 18:02
  • 1
    Note: it's not at all clear to me that those initial conditions suffice, though perhaps they do. As the $a_i$ grow, there's no apparent reason why the subscripts you get might not be lower than $1$. I tried to dodge that problem by declaring that all the $a_i$ below a certain point were $0$. Proving that the given conditions suffice would be a strong first move. – lulu May 26 '19 at 18:05

1 Answers1

4

The sequence is given in OEIS A046699, where it is called the meta-Fibonacci sequence. It starts $$1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, \\ 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 17, 18, 18, \\ 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, \\ 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 33, 34, 34, \\ 35, 36, 36, 36, 37 $$ It is remarked that $a_n=w(n-1)$ where $w(n)$ is the least $k$ such that $2^n$ divides $(2k)!$ After $1$, odd numbers appear once each and evens appear once more than the number of factors of $2$ in the number. I don't know how to prove that.

Ross Millikan
  • 374,822