Solving the piecewise recurrence $f_n=f_{n-1}+f_{n-2}$ for $f_{n-1}$ even, and $f_n=f_{n-1}-3f_{n-2}$ for $f_{n-1}$ odd

Question

How to solve this piecewise recurrence relation? $$ f_0=1\\ f_1=2\\ f_n = \begin{cases} f_{n-1}+\phantom{3}f_{n-2} & \text{if } f_{n-1} \text{ is even}\\ f_{n-1}-3f_{n-2} & \text{if } f_{n-1} \text{ is odd}\\ \end{cases} $$

Python code

f = []
f += [1]
f += [2]
for i in range(10):
    if f[-1]%2==0:
        f += [f[-1] + f[-2]]
    else:
        f += [f[-1] - 3 * f[-2]]
print(f)
---------------------------
[1, 2, 3, -3, -12, -15, 21, 66, 87, -111, -372, -483]

I learned the linear algebra (using eigenvectors) solution of "Solving homogeneous linear recurrence relations", but when a piecewise function appears, I still don't know how to solve it.

Appreciate your help!

Answer 1

Thanks everyone for the discussion. The problem has been solved, the idea is as follows.

$$\begin{align} f_0&=1\\ f_1&=2\\ f_2&=f_{1}+f_{0}=2+1=3,\quad for\ f_{1} \ is\ even\\ f_3&=f_2-3f_1=3-3\times2=-3,\quad for\ f_{2} \ is\ odd\\ f_4&=f_3-3f_2=-3-3\times3=-12,\quad for\ f_{3} \ is\ odd\\ f_5&=f_4+f_3=-12+(-3)=-15,\quad for\ f_{4} \ is\ even\\ f_6&=f_5-3f_4=-15-3\times(-12)=21,\quad for\ f_{5} \ is\ odd\\ f_7&=f_6-3f_5=21-3\times(-15)=66,\quad for\ f_{5} \ is\ odd\\ f_8&=f_7+f_6=66+21=87,\quad for\ f_{5} \ is\ even\\ ... \end{align}$$

we can observe, let $O(f_i)\rightarrow \{odd,even\}$ , we have \begin{align} O(f_0)=odd\\ O(f_1)=even\\ O(f_2)=odd+even=odd\\ O(f_3)=odd-3\times even=odd-even=odd\\ O(f_4)=odd-3\times odd=odd-odd=even\\ O(f_5)=odd+even=odd\\ ... \end{align}

Thus \begin{align} f_{3n-1}&=f_{3n-2}+f_{3n-3}, \quad O(f_{3n-1})=odd \\ f_{3n}&=f_{3n-1}-3f_{3n-2}\\ &=f_{3n-2}+f_{3n-3}-3f_{3n-2}\\ &=-2f_{3n-2}+f_{3n-3}, \quad O(f_{3n})=odd\\ f_{3n+1}&=f_{3n}-3f_{3n-1}\\ &=(-2f_{3n-2}+f_{3n-3})-3(f_{3n-2}+f_{3n-3})\\ &=-5f_{3n-2}-2f_{3n-3}, \quad O(f_{3n+1})=even\\ where\ n&\geq1\\ \end{align}

So we have

Verification

import numpy as np
n=19
a = np.array([[0,1,1],[0,1,-2],[0,-2,-5]])
c=np.linalg.eig(a)
d=c[1]
e=np.matmul(np.matmul(np.linalg.inv(d),a),d)
e_n = e**n
M_n = np.matmul(np.matmul(d,e_n),np.linalg.inv(d))
r = np.matmul(M_n, np.array([[0],[1],[2]]))
print(r[1])
----------------
[-1.06912433e+14]

f = []
f += [1]
f += [2]
for i in range(226):
    if f[-1]%2==0:
        f += [f[-1]+f[-2]]
    else:
        f += [f[-1] - 3 * f[-2]]
print(f[n*3])
----------------
-106912432560783