2
$\begingroup$

I am not a mathematician (but a computer scientist) and stumbled across the following in the analysis of an algorithm (Berthold Vöcking: How Asymmetry Helps Load Balancing). The author gives Knuth: The Art of Computer Programming Vol. 3 as a source for the golden ratio - but I could not find anything about the given relationship between the $d$-ary Fibonacci numbers and a generalized golden ratio in it, but would like to have a closer look at this. Google didn't help much either - probably because other names are used.

Here are the definitions and the relationship from the article:

Define $d$-ary Fibonacci numbers as follows: for $k\leq 0$, $F_d(k) = 0$, $F_d(1) = 1,\,$ and for $k\geq 0,\;$ $$F_d(k) = \Sigma_{i=1}^{d} F_d(k-i)$$

Define $\Phi_d = \lim_{k \rightarrow \infty} \sqrt[k]{F_d(k)}$

Then, $F_2$ corresponds to the usual Fibonacci numbers and $\Phi_2$ to the golden ratio and $\Phi_d$ is a generalization.

Can you point me towards a proof?

$\endgroup$
0
$\begingroup$

Use the explicit solution: http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients. Is a linear combination of exponentials.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.