12
votes
4answers
339 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
1
vote
4answers
132 views

Fibonacci Calculation using a larger matrix

So the formula to generate the fibonacci sequence in matrix form is: $$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & ...
3
votes
1answer
91 views

Using matrices to calculate fibonacci?

I have been told a couple of times it possible to calculate the fibonacci sequence much quicker using matrices but I never understood/they never elaborated. Would somebody be able to show how this ...
4
votes
2answers
692 views

How to prove Fibonacci sequence with matrices?

How do you prove that: $$ \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{pmatrix}$$
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
1
vote
1answer
86 views

Matrix powers and recurrence relations

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? ...
4
votes
1answer
271 views

The Principle of Mathematical Induction

The question is Let $( F_0, F_1, F_2,... )$ be the Fibonacci sequence defined by $F_0=0,\, F_1=1, and F_{n+1}=F_n+F_{n-1}$, n greater than or equal to 1. Prove the following identities. ...
3
votes
5answers
219 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
0
votes
2answers
109 views

Fibonacci Matrix

I'm looking for a good way to find the matrix form of fibonacci equation, and also a more general implementation. I've looked all other the web and haven't found it. I'll be really thankfull to any ...
2
votes
2answers
598 views

Recurrence for a lagged Fibonacci sequence

I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise? For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ ...