Fibonaaci Recurrence

Question

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities

Given Data in question

1. $F_n=F_{n-1}+F_{n-2}$, where $F_1=F_2=1$, we have $F_n= \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}}$ and generating function $g(x)= \sum_{n=0}^{\infty}F_nx^n=\frac{x}{1-x-x^2}$
2. More details of Fibonacci recursion and properties can be found here! .

Question

Can we find solution for a)$Q_n$(interms of n) b) $ g(x)= \sum_{n=0}^{\infty}Q_nx^n $ for the given recursion below $nQ_n=Q_{n-1}+Q_{n-2}\tag 3$ $Q_1=Q_2=1$,by using the above results, given the fact that both follows same recursion tree (in structure) even though results are different? if so please answer

NB :: This is not a home work problem. Logic is simple,the varying n will make it tough. And no prof will give it as home work. I am trying this for weeks/months.. It is not simple. Attempt on a similar problem by me can be found here

NB :: I know a method of using ODE. But I am trying to solve it with out ODE so that I can extent this to higher dimension like matrices in similar structure questions. Please avoid ODE solution

Answer 1

g'(x) = 1 + 2x + (1+x)g(x)

I am not giving the derivation in case this is a homework question, but it should be easy to work out.

Once you get this, you can solve this integral using standard techniques. Try wolfram:

http://www.wolframalpha.com/input/?i=g%27%28x%29+%3D+1+%2B+2x+%2B+%281%2Bx%29g%28x%29

Now to get $Q_n$ compare coefficients of x.

Answer 2

Calculating the $Q_n$ for $n=0\ldots 11$ gives,

$n!Q_n = A_n$ with $\{A_n\}_{n\in\mathbb N_0} = \{1,1,2,4,10,26,76,232,764,2620,9496,35696,\ldots\}$

at least the comments on

http://www.oeis.org

should give you some hints for the respective matching sequences.