Is there a general theorem to manipulate recursive functions? I was messing with some recursive functions and realized it was equivalent to the Fibonacci sequence, but I couldn't figure out why. I then played a little further, and discovered some other interesting patterns. Let's consider functions $A,B$.
Let $A(1) = 0$, $B(1) = 1$, $A(n) = B(n-1)$, $B(n) = A(n-1) + B(n-1)$. Then, $B(n) = B(n-2) + B(n-1)$, which causes $A(n) = A(n-1) + A(n-2)$. Of course, now both $A$ and $B$ are the Fibonacci sequence.
I was trying to figure out how this happened precisely, so I went back along the 
chain. I then discovered $B(n) = 2B(n-2) + B(n-3) = 2B(n-1) - B(n-3)$ and several other similar relations. What causes these relations to happen? Is there a general method of manipulating functions to get equalities?

(Not a complete answer, still maybe relevant.)  The recurrence can be written in  matrix form as:
$$
\begin{pmatrix}
 B_{n} \\
 A_{n}
\end{pmatrix}
=
\begin{pmatrix}
 1 & 1 \\
 1 & 0
\end{pmatrix}
\cdot
\begin{pmatrix}
 B_{n-1} \\
 A_{n-1}
\end{pmatrix}
\quad\quad \text{with}\;\;
\begin{pmatrix}
 B_{1} \\
 A_{1}
\end{pmatrix}
=
\begin{pmatrix}
 1 \\
 0
\end{pmatrix}
$$
It follows by telescoping (or induction) that:
$$
\begin{pmatrix}
 B_{n} \\
 A_{n}
\end{pmatrix}
=
\begin{pmatrix}
 1 & 1 \\
 1 & 0
\end{pmatrix}^{n-1} \cdot 
\begin{pmatrix}
 B_{1} \\
 A_{1}
\end{pmatrix}
$$
But $\displaystyle\; \begin{pmatrix}
 1 & 1 \\
 1 & 0
\end{pmatrix}^{n-1} 
= 
\begin{pmatrix}
 F_n & F_{n-1} \\
 F_{n-1} & F_{n-2}
\end{pmatrix}  
\;$ (see this for example), so in the end:
$$
\begin{pmatrix}
 B_{n} \\
 A_{n}
\end{pmatrix}
=
\begin{pmatrix}
 F_n & F_{n-1} \\
 F_{n-1} & F_{n-2}
\end{pmatrix}  
\cdot 
\begin{pmatrix}
 1 \\
 0
\end{pmatrix}
=
\begin{pmatrix}
 F_n \\
 F_{n-1}
\end{pmatrix}
$$
