The Fibonacci Sequence, Part 2

The last time I wrote about the Fibonacci sequence, I mentioned an explicit formula giving the numbers of the sequence.  That post made me think back on another problem, one for which I had already come up with a method that I believed would solve the problem, although I never followed through on it completely.
What if the sequence didn't start with 1, 1?


I figured I would have a variable for the ratio of the first and second numbers, and then have a variable for the scale factor.

So A would cover all the different multiples of the same sequence (like, double A to change 1,1,2,3 to 2,2,3,6, triple it for 3,3...).  Then if B covered all possible ratios of the first two numbers (like, 1,2; 1,3; 1,4; 1,1/2; 1,-99999; etc), then an equation of this form could be used for any sequence in which the next number was the sum of the last two.  So basically I had to show that the range of the function y= (P-Qx)/(1-x) was all real numbers (with P=(1+sqrt(5))/2, Q=(1-sqrt(5))/2, and using x as the "B," the variable that you change, resulting in different y's, which was the ratio of the 1st and 0th numbers, in this case [when I actually did this a while ago, I did the ratio of the 2nd and 1st numbers, but it's a little more complicated, and this way is good enough.  If you have complaints about it being the 0th and 1st numbers, change that n in the above formula to n-1...].

So anyway, (P-Qx)/(1-x).  If I found the inverse, I could use that to calculate the value for B in the above equation.  I recalled a trick from my old Pre-calculus class (here it is in full detail and without skipping steps, because I liked this part (and it's easier to understand...)):

So if you wanted the 1st number divided by the 0th number of your sequence to be, say, 3, then you just plug in 3 for y and use what you get as x as that "B".  (If you wanted it to be infinity, i.e. the 0th number is 0, then you "plug in an infinity" for y.  In other words, x would just be 1.)
So you want your sequence to be 1, 100, 101, 201...?  The ratio is 100, so B becomes 1-(P-Q)/(100-Q), and then to make the 0th number equal 1, A would have to be such that A*(1-B)=1, so A=1/(1-B).  You want your sequence to be x, y, x+y, y+x+y...?  B=1-(P-Q)/((y/x)-Q), A=x/(1-B).

Now I would write my "theorem":

For the sequence in which the next number is the sum of the last two, and in which the first number is x and the second number is y, an explicit formula is

And there was still more.  What if you wanted a sequence in which the next number was the sum of the last 3 terms?  Or the last term plus 2 times the term before that?
The funny thing is that in the same time period I had looked at a Life board trying to figure out the probability that you would land on any given space.  Well if the space is 1 space away, it's 1/10.  2 spaces makes it 1/10th the probability of the last space plus 1/10.  N spaces away is 1/10th the sum of the probability of the last 10 numbers.  So it's like a sequence in which you add 1/10th the last 10 numbers to get the next number, hey-

Somehow, I came to the conclusion that if you have a sequence in which the next number xn=sum(ai*xn-i), i = 1, 2..., then you have to solve the polynomial equation x^n=sum(ai*x^(n-i)).  For example, for Fibonacci, you solve x^2=x+1.  And then you take the solutions, and put them to the nth power to get the nth number in the sequence.  Something like:

Where the a's are constants that give different starting values and the r's are the solutions to the polynomial equation.  Oh yeah and then something like with double roots the two terms would be a*(r^n) and a*n*(r^n)  [implying that triple roots would have a*n^2*r^n... so on...]...

If you're like, actually interested in an actual explanation for any of this, you can ask for one.  I feel like I could prove most of this, but it was probably true, and that was good enough for me, so...

And then there's the question: well what about if the next term is the last term squared?  Which leads directly into a problem I intended to solve two semesters ago...  [to be continued]