How to solve linear recurrence relation based on conditions?

Question

Given

$F(n)=a\cdot F(n-1)-b$ ,$n$ even

$F(n)=a\cdot F(n-1)+b$ ,$n$ odd

$F(0),a,b$ are constants.

How to calculate $n$-th term in $log(n)$ time?

I learnt matrix exponentiation technique. But problem is that the transformation matrix changes in each step

Can it be used here?

Answer 1

Write F(n) in terms of F(n-2) separately for even and odd n.

For even n, $F(n) = a F(n-1)-b = a(aF(n-2)+b)-b =a^2F(n-2)+ab-b $ and similarly for odd n.

Then treat even and odd n F as independent sequences.

(added later)

Letting $g(n) = F(2n)$ and $h(n) = F(2n-1)$, the recurrences are

$F(2n) =a^2F(2n-2)+ab-b $ so $g(n) = a^2g(n-1)+ab-b $ and, for odd n, $F(n) = a F(n-1)+b = a(aF(n-2)-b)-b =a^2F(n-2)-ab+b $ so $F(2n+1) =a^2F(2n-1)-ab+b $ so $h(n) = a^2h(n-1)-ab+b $.

Both of these are of the form $r(n) = ur(n-1)+v $.

I like to solve them by turning them into a telescoping sum this way.

If $u = 1$ then it is $r(n) = r(n-1)+v $ so $r(n) = nv+r(0)$. Otherwise divide by $u^n$ to get $\dfrac{r(n)}{u^n} =\dfrac{r(n-1)}{u^{n-1}}+\dfrac{v}{u^n} $ or $\dfrac{r(n)}{u^n}-\dfrac{r(n-1)}{u^{n-1}} =\dfrac{v}{u^n} $.

This telescopes nicely and we get

$\begin{array}\\ \dfrac{r(m)}{u^m}-r(0) &=\sum_{n=1}^{m-1}(\dfrac{r(n)}{u^n}-\dfrac{r(n-1)}{u^{n-1}})\\ &=\sum_{n=1}^{m-1}\dfrac{v}{u^n}\\ &=\dfrac{v}{u^m}\sum_{n=1}^{m-1}u^{m-n}\\ &=\dfrac{v}{u^m}\sum_{n=1}^{m-1}u^{n}\\ &=\dfrac{v}{u^m}\dfrac{u-u^m}{1-u}\\ \end{array} $

so $r(m) = r(0) u^m+v\dfrac{u-u^m}{1-u} $.

If $u < 1$ then $r(m) \to \dfrac{vu}{1-u} $; if $u > 1$ then

$\begin{array}\\ \dfrac{r(m)}{u^m} &= r(0) +v(\dfrac{u^{-m+1}}{1-u}-\dfrac{1}{1-u})\\ &\to r(0) -\dfrac{v}{1-u}\\ \end{array} $

Answer 2

Note that this is nothing but $F(n)=aF(n-1)+(-1)^{n+1}b.$ If $a=0,$ you have the solution for the recurrence. Otherwise note that $$\dfrac{F(n)}{a^n}-\dfrac{F(n-1)}{a^{n-1}}=\dfrac{(-1)^{n+1}b}{a^n}$$ and telescope. For the series in RHS you can use the geometric series formula.