I thought about one relation while doing some other problem -

$ \displaystyle f_{n}(x) = x(f_{n-1}(x) + f_{n-2}(x)); \ f_0(x) = 1, f_1(x) = x $

I don't know the general procedure to solve such relations. What I tried is to compare the coefficients on both sides and get a recurrence for each of them.

$ [x^{n}]{f_{n}(x)} = [x^{n-1}]{f_{n-1}(x)} + [x^{n-1}]{f_{n-2}(x)} $

$ [x^n]{f_{n}(x)} = 1 $


$ [x^{n-1}]{f_{n}(x)} = [x^{n-2}]{f_{n-1}(x)} + [x^{n-2}]{f_{n-2}(x)} $

$ [x^{n-1}]{f_n(x)} = n-1 $


$ [x^{n-2}]{f_n(x)} = \dfrac{(n-2)(n-3)}{2} $

$ [x^{n-3}]{f_n(x)} = \dfrac{(n-4)(n-5)(n-6)}{6} $

Now, a general formula can be found relating coefficients.

$ \displaystyle [x^k]{f_n(x)} = \sum_{m}^{n-k}{[x^{k+1}]{f_m(x)}}$


$ \displaystyle f_n(x) = x^n + \frac{(n-1)}{1!} x^{n-1} + \frac{(n-2)(n-3)}{2!} x^{n-2} + \frac{(n-3)(n-4)(n-5)}{3!} x^{n-3} + \cdots $

You can write it in rising/falling factorial if you like that notation.

This function looks interesting. And I would like to investigate more of its properties but I don't know what/how to search for.


Consider a second variable $y$, and rewrite the sequence as $f_0 = 1$, $f_1 = x$, and $f_n = x f_{n-1} + xyf_{n-2}$. Then each $f_n$ is homogeneous of degree $n$ in $x, y$. Then consider the formal series $f_0 + f_1 + f_2 + \cdots$. By rearranging the terms, you will find that this is a geometric series, equal to $1 + x(1+y) + \big(x(1+y)\big)^2 + \cdots$. If you expand this, you take the homogeneous parts of degree $0, 1, ...$ and specialize to $y=1$ you will find your original sequence. This is also why you get the binomial coefficients which you already found on your own.

  • $\begingroup$ That seems quite random but nice. Maybe that's one of the way to approach polynomial recurrence. Anyways, don't you think the function looks kinda beautiful and must be discussed if it has already not. $\endgroup$ – Kartik Sharma Aug 27 '16 at 16:46

Just consider your $x$ as a fixed value, and solve the resulting recurrence. You get the generating function $F(z) = \sum_{n \ge 0} f_n(x) z^n = \frac{1 - x - z}{1 - x z - x z^2}$. Next step is to expand as partial fractions and read off coefficients. Sadly, the denominator doesn't factor nicely (was to be expected, for $x = 1$ this is the shifted Fibonacci recurrence).


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.