Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Base Case:

$$ \left\{ \begin{array}{c} T(1) = 1 \\ T(2) = 1 \\T(3) = 4\end{array} \right. $$

I have the system:

$$ \left\{ \begin{array}{c} T(N) = G(N-1) + F(N-1) \\ G(N) = F(N-1) + G(N-1) \\ F(N) = 2H(N-1) + F(N-2) \\ H(N) = H(N-1) + F(N-1)\end{array} \right. $$

I seems $$T(N) = H(N) = G(N)$$ so we now have only two equations:

$$ \left\{ \begin{array}{c} T(N) = T(N-1) + F(N-1) \\ F(N) = 2T(N-1) + F(N-2)\end{array} \right. $$

I figured

$T(N) = T(N-k) + \sum_{i=1}^k F(N-i) $

and

$F(N) = F(N-2) +2T(N-k) + 2\sum_{i=2}^k F(N-i) $

But after mixing these expressions in a similar way, I came unstuck.

I tried following another example but it didn't help.

I would like to find $T(10^{12})$. Probably by using matrix exponentiation.

share|improve this question
    
use latex please..... –  Learner Oct 29 '12 at 5:24
    
Ok, I'm just reading a latex tutorial now, will update soon –  robert king Oct 29 '12 at 5:26
    
I've now added latex –  robert king Oct 29 '12 at 5:45
    
NICE!!!!!!!!!!! –  Learner Oct 29 '12 at 5:46
    
fixed a typo, it should have been F(N-2) not F(N-1) –  robert king Oct 29 '12 at 5:50

2 Answers 2

up vote 4 down vote accepted

Note that

$$ \begin{pmatrix} T_n \\ F_n \\ F_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 \\ 2 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} T_{n-1}\\ F_{n-1}\\ F_{n-2} \end{pmatrix}. $$

So starting with $(T_1, F_1, F_0)$ you can find $(T_n, F_n, F_{n-1})$ quickly by matrix exponentiation. The latter can be done by the squaring method.

share|improve this answer
    
beautifully simple isn't it? –  robert king Nov 3 '12 at 2:25

Since $T(N)=T(N-1)+F(N-1)$ so $$2T(N)=2T(N-1)+2F(N-1)$$ minus this $F(N)=2T(N-1)+F(N-1)$ you get $$2T(N)-F(N)=F(N-1)$$ which means $$T(N)=\frac{1}{2}(F(N)+F(N-1))$$ so by institution it back to $F(N)=2T(N-1)+F(N-2)$ for $N-1$, you get $$F(N)=F(N-1)+2F(N-2)$$ Using the base case we have $$2T(1)=F(1)+F(0)=2$$ Also $$2T(2)=F(2)+F(1)=F(1)+2F(0)+F(1)=2(F(1)+F(0))=2$$ So there is an inconsistency in the base case you gave.

share|improve this answer
    
would you like to take this to private chat quickly? (if math.stackexchange has that feature) –  robert king Oct 29 '12 at 6:33
    
Don;t know how to do a chat. I think if you can find the initial values for F, then it maybe solved. –  user46090 Oct 29 '12 at 6:38
    
I think T(3) should be 3. I formulated all my equations incorrectly btw (for what i was trying to solve). I know how to correct everything though. –  robert king Oct 30 '12 at 21:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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