I was doing a problem for a math competition

How many five digit integers satisfy the following:
- All the digits are odd
- The difference between adjacent digits is 2
An example of such a number is 13535 or 57979

...and wanted to generalize it to "How many answers satisfy the conditions for n-digits"?

For example, given one digit, there are 5 possibilities {1, 3, 5, 7, 9}...
and given two digits, there are 8 possibilities {13, 31, 35, 53, 57, 75, 79, 97},
etc.

I managed to figure out a solution that didn't involve drawing out ridiculously large probability trees to brute-force the answer, but I want to know if there's an algorithmic or better way to solve the problem. 

Here's my solution below (it's an exact copy of an email I sent to my teammates), but I don't really understand why my solution works. (spoiler'd for length).

If you need a closed form expression...

Note that {a_i}_i=1 = {e_i}_i=1 via symmetry, and likewise {b} = {d}. We can consider the finite state diagram
a <-> b <-> c <-> d <-> e which is symmetric on c.

Now, we may reexpress each recursion:
a_n+1=b_n
b_n+1=a_n+c_n
c_n+1=2b_n

Notably, this means we can express a and c directly in terms of sequence b. So it logically follows that we should try substituting those out in the recursion for b:
b_n+1=3b_n-1

The characteristic polynomial of this recursion is λⁿ⁺¹=3λ^n-1 => λ²-3=0.

In other words the roots are λ = sqrt(3) and -sqrt(3). What does this mean?

Well, this means that we can express sequence b in terms of a linear combination of exponential functions, namely sqrt(3)ⁿ and (-sqrt(3))ⁿ.
In layman terms, b_n=A*sqrt(3)ⁿ+B*(-sqrt(3))ⁿ.

It is not hard to calculate this; we already know that b₁=1 and (easily computed) b₂=2.

So we just solve a system of linear equations;
1=A*sqrt(3)-B*sqrt(3) => sqrt(3)/3 = A-B

2=3A+3B => 2/3 = A+B
resulting in A=(2+sqrt(3))/6 and B=(2-sqrt(3))/6.

Thus we have
b_n=(2+sqrt(3))/6*sqrt(3)ⁿ+(2-sqrt(3))/6*(-sqrt(3))ⁿ.

But the million dollar question remains. We don't want the value of a_n, b_n, OR c_n; we want the sum!

Well, we add 2a_n+2b_n+c_n; the 2 is because we copied d and e over. We reexpress the a and c terms into b because we already have a form ready.

So we have
Σ_n=2b_n+4b_n-1=[(2+sqrt(3))/6*(2+4/sqrt(3))]*sqrt(3)ⁿ+[(2-sqrt(3))/6*(2-4/sqrt(3))]*(-sqrt(3))ⁿ

=[4/3+7sqrt(3)/9]*sqrt(3)ⁿ+[4/3-7sqrt(3)/9]*(-sqrt(3))ⁿ

(Caveat; Σ₁=5, not 14/3; this occurs because the formulas for sequence b refers to a term 2 terms in advance, effectively drawing from the -1st term which is obviously invalid)

The sequence goes: 5,8,14,24,42,72,126,216,378,648,1134,...

Notice anything interesting? No?

I'll show it again. 5,8,14,24,42,72,126,216,378,648,1134,...

Ohey, every other term it triples! Partially due to how the structure of the recursion itself (with λ²-3=0 as a characteristic polynomial), but there in fact is a combinatorial interpretation! (Not all the algebraic sludgework QQ)

It all lies in PARITY. In fact, there are two mechanisms syncing together, digit parity and positional parity. While in the traditional sense, parity refers to evenness or oddness of numbers, since all digits are odd that's not going to be of much use. Instead we consider mod 4 parity, which helps separate the digits better (so 159 and 37). Positional parity refers to the evenness/oddness of the positional index of a particular string.

Well, as luck would have it, you're colorbound like a bishop on a chessboard! Congratulations. As a visual:
..13579
A■□■□■
B□■□■□
A = odd position
B = even position

As it turns out, if you start at a black square, you're condemned to the color that you start on, as each consecutive digit means a position change, and since they differ by 2, it's also digit parity change! So the two color-changing operations cancel out and you're back to square one.

This makes our task easier.

..13579
A■□■□■
B□■□■□
C■□■□■

Without loss of generality, assume that you start on a white square. As symmetry applies, both A3 and A7 have the same number of possibilities. Starting from A3 you can either go A3-B3-C3, A3-B5-C3, or A3-B5-C7. Starting from A7, you can get to C7 twice and C3 once. Adding them up, you round out to C3 receiving a path thrice, and C7 also receiving a path thrice. Hence the number triples every two turns.

The only thing is, that you can't really start on a black square and immediately expect a triple; the mechanism doesn't quite work like that. You have to wait until the second turn before you start tripling.