# RSolve not reducing for a certain recurrence relation

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?

• Try replacing the next-to-last term in RSolve (a) with a[n]. – yosimitsu kodanuri Nov 26 '18 at 20:30
• It still simply echoes the input: RSolve[{a[0] == 1, a[1 + 2 n] == 2 a[2 n], a[2 n] == 2 + a[-1 + 2 n]}, a[n], n] – konsolas Nov 26 '18 at 20:36
• Welcome to Mathematica.SE! Interesting question(+1). I hope you will become a regular contributor. To get started, 1) take the introductory tour now, 2) when you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge, 3) remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign, and 4) give help too, by answering questions in your areas of expertise. – bbgodfrey Nov 27 '18 at 0:28

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.

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} *)

• Hi, thanks for the alternative solution. Do you know why Mathematica was unable to evaluate the input given? – konsolas Nov 26 '18 at 20:36
• Don’t know. Presumably the algorithms used are not sufficiently robust to cover this case. – Bob Hanlon Nov 26 '18 at 20:52