1
$\begingroup$

Let $d$ be a nonnegative integer, and let the sequence ${F_d(n)}$ be defined as follows:

$F_d(n) = 1$ for $n = 0, 1, \ldots, d$

$F_d(n) = F_d(n-1) + F_d(n-1-d)$ for $n>d$

For $d=0$ the sequence becomes:

$F_0(n) = F_0(n-1) + F_0(n-1)$ for $n>0$ and $F_0(0)=1$,

so it is a sequence of powers of $2$.

For $d=1$ the sequence becomes:

$F_1(n) = F_1(n-1) + F_1(n-2)$ for $n>1$ and $F_1(0) = F_1(1) = 1$,

so it is a Fibonacci sequence.

For $d=2$ the sequence is known as Narayana's cows sequence.

The sequence looks quite interesting to me, but for now I'm particularly interested in how fast it grows. To be more specific, I want to be able to calculate the number of digits of $F_d(n)$ for arbitrary $d$ and $n$ ($n$ can be very big). I can do it for $d=0$ and $d=1$, since I know the closed formula for $F_d(n)$ in those cases. But what about arbitrary $d$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Let $\gamma$ be the largest (real) root of $x^{d+1} -x^d - 1 = 0$. Then $F_d(n) \sim \gamma^n$, and the aymptotics are easy to work out. $\endgroup$
    – David Handelman
    Commented Feb 7, 2015 at 17:36
  • $\begingroup$ MO is a website for questions of math research, and I don't see the research angle to these questions. Probably better to ask elsewhere. $\endgroup$
    – Gerry Myerson
    Commented Feb 7, 2015 at 22:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .