How to define a recursive sequence

Question

I would appreciate if somebody could help me with the following problem:

Q: How to define this in Mathematica.

$$a_{n+1}=\begin{cases} a_{n} & ,a_{n} \ge n\\ 2n-a_{n}& ,a_n<n \end{cases},\: a_{1}=2$$

Answer 1

There is an elegant solution to this problem. Here is how I used Mathematica to find it.

I started with a direct translation of the question definition of $a_{n+1}$ into a recursive function with memoization.

a[1] = 2;
a[n_ /; a[n - 1] >= n] := a[n] = a[n - 1]
a[n_ /; a[n - 1] < n] := a[n] = 2 n - a[n - 1]

Then I looked at the first 20 values:

Table[a[n], {n, 1, 20}]

{2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20}

By inspection, I concluded that a can be rewritten in the simpler form

Clear[a]
a[n_?EvenQ] := n
a[n_?OddQ] := n + 1

Can Mathematica find a solution directly? It can if we give a sequece of results generated by ato FindSequenceFunction. Mathematica, of course, won't find a function definition like the one above since it looks for a single expression not involving any predicate testing.

b = FindSequenceFunction[Table[a[n], {n, 1, 20}]]

1/2 (-1)^#1 (-1 + (-1)^#1 + 2 (-1)^#1 #1) &

Is this equivalent to the definition of a. Yes, it is, which can be proven by evaluating

Reduce[b[2 k] == 2 k && b[2 k - 1] == 2 k, k, Integers]

k ∈ Integers

That is to say a and b are them same for all integer values.

Answer 2

How about this using Piecewise