RSolve not reducing for a certain recurrence relation

Question

I'm trying to use RSolve as follows to solve a recurrence relation:

RSolve[{a[0] == 1, a[2 n + 1] == a[2 n]*2, a[2 n] == a[2 n - 1] + 2}, a, n]

I think the meaning of the relation is clear: for odd terms in the sequence, multiply the previous term by two, and for even terms, add two to the previous term.

However, when evaluating this, Mathematica simply echos the input:

rather than attempting to solve the recurrence.

I can't find anything in the RSolve documentation which talks about cases where RSolve will do nothing, without any error message.

Have I made a syntax error, or does this mean that Mathematica is not able to solve this type of recurrence relation? How can I change my input so that Mathematica does solve the recurrence, assuming it is possible?

Answer 1

It appears that RSolve cannot solve difference equations in which two different equations describe the same variable. If so, a work-around is to represent a[k] with k an even index as c[k], and with k an odd indix as b[k], so that there is only one equation per variable.

FullSimplify[RSolveValue[{c[0] == 1, b[k] == c[k - 1]*2, c[k + 2] == b[k + 1] + 2}, 
    {c[k], b[k]}, k] /. C[1] -> 0]
(* {-2 + 3 2^(-1 + k/2) (1 + (-1)^k), -4 - 3 2^(1/2 (-1 + k)) (-1 + (-1)^k)} *)

Then, construct the desired a[k] as even-index terms of c[k] and odd-index terms of b[k].

sol[k_] := If[EvenQ[k], -2 + 3 2^(k/2) , -4 + 3 2^((1 + k)/2) ]
Table[sol[k], {k, 0, 10}]
(* {1, 2, 4, 8, 10, 20, 22, 44, 46, 92, 94} *)

as desired.

Answer 2

When Mathematica returns the input without any error message, it is unable to evaluate the input.

With this particular recursion there is another approach. The recursion can be defined by

Clear[a, ar]

ar[0] = 1; ar[n_?OddQ] := ar[n - 1]*2; ar[n_?EvenQ] := ar[n - 1] + 2;

Generating a sequence from this recursion

seq = ar /@ Range[10]

(* {2, 4, 8, 10, 20, 22, 44, 46, 92, 94} *)

Use FindSequenceFunction to find the closed form of the recursion

a[n_] = FindSequenceFunction[seq, n] // FullSimplify

(* -3 + (-1)^n + 3 2^(-1 + n/2) (1 + Sqrt[2] + (-1)^(1 + n) (-1 + Sqrt[2])) *)

Checking equivalence outside of the range of seq

And @@ Table[a[n] == ar[n], {n, 0, 100}]

(* True *)

EDIT: Verifying,

Simplify[{a[2 n + 1] == a[2 n]*2, 
  a[2 n] == a[2 n - 1] + 2}, {Element[n, Integers], n >= 0}]

(* {True, True} *)