# Recurrence relation in a table

I am trying to generate a list of x-values for a function using a module, where my x-value must increase by 'a' if the term number is even, and by 'y' if it is odd. However, x[1] is 0.

For example: $x_1 = 0, x_2 = a, x_3 = a+y, x_4 = 2a+y, x_5 = 2a+2y...$you get the point.

I am attempting to use a recurrence relation within an If-clause to generate values of $x_n$. However, my code does not work.

My code is:

 XValues[counter_] :=
Module[{a, y, xvalues, x},

x[1] -> 0;

xvalues =
Table[x[j] -> If[OddQ[j] == True , x[j - 1] + y, x[j - 1] + a], {j, 2, counter}];

Flatten@{x[1] -> 0, xvalues}
]


However, if I evaluate the module for a certain number, I get the following:

{ x$10387[1] -> 0, x$10387[2] -> a$10387 + x$10387[1],
x$10387[3] -> y$10387 + x$10387[2], x$10387[4] -> a$10387 + x$10387[3],
x$10387[5] -> y$10387 + x$10387[4]}  I think it is probably to do with protected variables or something along those lines, but I am not sure. Any ideas would be gratefully received! Thanks. ---------------------EDIT--------------------- Thanks for all the answers! @Teake Nutma I have used your algorithm in a module to generate the values as it seems most appropriate to what I want to do with the x values. XValues[counter_] := Module[{xvalues}, xsubstitute[1] = 0; xsubstitute[i_Integer?EvenQ] := xsubstitute[i] = xsubstitute[i - 1] + a; xsubstitute[i_Integer?OddQ] := xsubstitute[i] = xsubstitute[i - 1] + y; xvalues = Table[xsubstitute[i], {i, 1, counter}] ]  I now want to replace the x value in the Phi functions of the equations generated below with the x value generated through the XValues module (so a different value of x for each 'Eq' generated). This is my attempt so far but it does not appear to work. Any ideas? simeqs = Table[Eq[j] -> Phi[j] == Phi[j + 1] /. x -> xsubstitute[j]/. eqs , {j, 2*number}];  - Those$10387 etc. appear because You are scoping a, x and y. What do You want to get, if list of values why are You using ->? –  Kuba Jul 13 '13 at 14:24
as an aside: another approach might be: f[n_] := Plus @@ (Through[{Floor, Ceiling}[(n - 1)/2]] {y, a}) or similar –  Pinguin Dirk Jul 13 '13 at 15:00
@PinguinDirk please, post it, I want to upvote this :) –  Kuba Jul 13 '13 at 15:11

It is a misconception to use a recurrence table here.

I'd define simply:

f[n_Integer] := IntegerPart[n/2] a + IntegerPart[(n - 1)/2] y


then it cannot be overcome by anything else

f /@ Range[7]

{0, a, a + y, 2 a + y, 2 a + 2 y, 3 a + 2 y, 3 a + 3 y}


Edit

If we prefer to generate lists automatically, this can be supplemented by

SetAttributes[f, Listable]


now it can yield appropriate parts of a table, e.g.:

f[ Range[2^32, 2^32 + 7] ]

{2147483648 a + 2147483647 y, 2147483648 a + 2147483648 y,
2147483649 a + 2147483648 y, 2147483649 a + 2147483649 y,
2147483650 a + 2147483649 y, 2147483650 a + 2147483650 y,
2147483651 a + 2147483650 y, 2147483651 a + 2147483651 y}

-
It may be a misconception but it is not a bad idea if it can be faster. :) –  Kuba Jul 13 '13 at 15:51
To see the key point try e.g. your g[2^31+11] and f[2^31+11]. In general, recurrence based solutions are elegant, but if they are unnecessary we'd better functional solutions. –  Artes Jul 13 '13 at 16:01
If You want to compare, I should rather try f/@Range[2^31+11]. Don't get me wrong, Your approach is of course the best for getting single value from this sequence but OP want all the list up to n. –  Kuba Jul 13 '13 at 16:10
I know, I agree ;) But in case of whole list try: g[10^5]; // Timing and f /@ Range[10^5]; // Timing –  Kuba Jul 13 '13 at 16:19
@Artes Thanks for your response, your idea of defining it in a non recursive way was very helpful as it meant that I could easily access high terms of the sequence. –  CJO Jul 13 '13 at 18:13

(I am aware that this is no answer to your question, it just presents another approach to solve the problem as such - I hope it helps!)

Based on the nature of your "recurrence", you could calc directly:

f[n_] := Plus @@ (Through[{Floor, Ceiling}[(n - 1)/2]] {y, a})


Let me know if you need any explanation.

Output:

f /@ Range[10]


{0, a, a + y, 2 a + y, 2 a + 2 y, 3 a + 2 y, 3 a + 3 y, 4 a + 3 y, 4 a + 4 y, 5 a + 4 y}

-
It helps ;) add a line with f /@ Range[10] –  Kuba Jul 13 '13 at 15:19
ok thanks, and this wasn't meant to be fast or anything, just to question the recurrence :) –  Pinguin Dirk Jul 13 '13 at 15:23
It is not the fastest but I like the syntax :) –  Kuba Jul 13 '13 at 15:28

This is the fastest way from what I've tested so far:

g[i_] := Accumulate@Prepend[
Riffle@@(ConstantArray[##] & @@@ {{a, Ceiling[(i - 1)/2]},
{y, Floor[(i - 1)/2]}})
, 0];

g[10]


{0, a, a + y, 2 a + y, 2 a + 2 y, 3 a + 2 y, 3 a + 3 y, 4 a + 3 y, 4 a + 4 y, 5 a + 4 y}

Edit

Another way for generation whole list. Similar to Teake Nutma's but quite fast.

h[1] = 0; sum=0;
h[x_?OddQ] := sum + y;
h[x_?EvenQ] := sum + a;
(sum = h[#]) & /@ Range[10]


{0, a, a + y, 2 a + y, 2 a + 2 y, 3 a + 2 y, 3 a + 3 y, 4 a + 3 y, 4 a + 4 y, 5 a + 4 y}

-

Instead of using a Module you could also do the following:

x[1] = 0

x[i_Integer?EvenQ] := x[i] = x[i - 1] + a
x[i_Integer?OddQ] := x[i] = x[i - 1] + y

xvalues = Table[x[i], {i, 1, 6}]
(* {0, a, a + y, 2 a + y, 2 a + 2 y, 3 a + 2 y} *)


But as @Artes points out, recursion doesn't make much sense performance-wise as a and y are the same at each step.

-