Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / c

Adding the Fibonacci recurrence and the identical recurrence relation for the Lucas numbers givesLinearity preserves this linear recurrence relation; the initial values come from $0+2$ and $1+1$.

Let $\varphi =(1+\sqrt{5})/2$, the golden ratio. Since ${\varphi }^2=\varphi +1$, multiplication by ${\varphi }^n$ gives ${\varphi }^{n+2}={\varphi }^{n+1}+{\varphi }^n$. Adding this recurrence relation to the one for $A_n$ yieldsThus the extra exponential term changes the initial values, but not the linear recurrence relation.