1
$\begingroup$

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.

  • 0
    use latex please.....2012-10-29
  • 0
    Ok, I'm just reading a latex tutorial now, will update soon2012-10-29
  • 0
    I've now added latex2012-10-29
  • 0
    NICE!!!!!!!!!!!2012-10-29
  • 0
    fixed a typo, it should have been F(N-2) not F(N-1)2012-10-29

2 Answers 2

4

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.

  • 0
    beautifully simple isn't it?2012-11-03
1

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.

  • 0
    would you like to take this to private chat quickly? (if math.stackexchange has that feature)2012-10-29
  • 0
    Don;t know how to do a chat. I think if you can find the initial values for F, then it maybe solved.2012-10-29
  • 0
    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.2012-10-30