# Computing a sequence by recurrence

I am trying to create a list where each element of the list is calculated using the sum of all previous elements of the list and also uses the $N$th element of another list. The initial value of the list is a known quantity. $k1$ is simply a constant value. $k2$ is a known list of $N$ elements.

$\quad \quad Q_N=\sum_{i=0}^{N-1}{k1(Q_i/k2_N)},\,N>0$ $\quad \quad Q_0=k0$

I'm not quite sure how to code this. I think the Nest function is somewhat close to what I want, but I need to keep plugging in the sum of all previous values, not just the previous value.

Any help would be greatly appreciated.

Edit: As I keep digging, FoldList seems like it might be useful, but I just can't seem to crack this problem.

Edit 2: It may be relevant that $N$ is going to be rather large. The context is a numeric solution to the time evolution of a system. So I want to have smaller time-steps, which leads to a large number of elements.

• Try something like Accumulate? reference.wolfram.com/language/ref/Accumulate.html – Chen Stats Yu Jan 9 '15 at 14:23
• Accumulate looks interesting. I'll read up on that. Thanks! – matt Jan 9 '15 at 14:25
• Ultimately, do you only need Q[N] or all Q[i] for 0 ≤ i ≤ N? – Martin Ender Jan 9 '15 at 15:38
• Ultimately, I will need all Q[i]'s, but just getting Q[N] would be a great start. – matt Jan 9 '15 at 15:41
• Is k1 an arbitrary function? If yes, then FoldList which seemed to be the way to do it no longer works. – FJRA Jan 9 '15 at 15:58

q[0] = 1;
k2 = {1,2,3,4,5};
q[n_] := q[n] = Sum[k1 q[i]/k2[[n]], {i, 0, n - 1}]

q /@ Range@5
(*{5, 15, 35, 70, 126}*)

• You should note that this is still $O(n)$. It's nice and simple though. – Martin Ender Jan 10 '15 at 20:45
• Wow, this is very slick. This was actually one of my first thoughts. There is a tutorial in the documentation called Functions That Remember Values They Have Found. I couldn't initially wrap my brain around it, but now I see how simple it is. I'm assuming that your value of k1 is 5. I would appreciate if you could confirm that, as I am making sure I understand this fully. Also, I posted another question that has to do with this situation. This would be a good answer to that if you want to put it up there too. mathematica.stackexchange.com/questions/71432 – matt Jan 12 '15 at 15:10
• Ummm. Scratch my above comment. I meant to say, this is $O(n^2)$, not $O(n)$. – Martin Ender Jan 12 '15 at 16:08

Here is one way to do it using FoldList. It will give you a list of all $Q_i$ for $0 < i \le n$.

n = 5;
k0 = 1;
k1 = 5;
k2 = {1, 2, 3, 4, 5};
FoldList[
(k2[[#2]] + k1)#/k2[[#2 + 1]] &,
k0 k1/k2[[1]],
Range[n - 1]
]
(* {5, 15, 35, 70, 126} *)


An important observation, which reduces the runtime from $O(n^2)$ to $O(n)$: for $i > 1$ we have

$$Q_N = \sum_{i=0}^{N-1} \frac{k_1 Q_i}{k_{2,N}} = \sum_{i=0}^{N-2} \frac{k_1 Q_i}{k_{2,N}} + \frac{k_1 Q_{N-1}}{k_{2,N}} = \frac{k_{2,N-1}}{k_{2,N}}\sum_{i=0}^{N-2} \frac{k_1 Q_i}{k_{2,N-1}} + \frac{k_1 Q_{N-1}}{k_{2,N}} = \frac{Q_{N-1}}{k_{2,N}}(k_{2,N-1}+k_1)$$

Note that this doesn't hold for $Q_1$, which is why we start the folding from there, instead of $Q_0$, such the first call of the function computes $Q_2$.

This observation lets us compute $Q_N$ solely based on $Q_{N-1}$, instead of having to look at all previous $Q_i$. The function inside the FoldList computes exactly this expression, where # is $Q_{N-1}$ and #2 is $N$.

Lastly, we fold onto a range of $i$ values, which we need to index into the $k_2$ list.

• When I try to run your code, I get an error that has to do with the #k2 part. It says Part 2 (and 3 and 4) of #k2 does not exist. I simply copied and pasted your code into a newly started kernel, so that there wouldn't be any errors from stuff I had tried. I am running Mathematica 10.0. – matt Jan 9 '15 at 16:43
• @matt Sorry, I accidentally swapped two characters. – Martin Ender Jan 9 '15 at 16:53
• Thank you very much. I am still working on understanding what is going on, but your example is working on my machine with that last edit. – matt Jan 9 '15 at 16:55
• @matt If it helps, think of # as $Q_{N-1}$ and of #2 as $N$. – Martin Ender Jan 9 '15 at 16:57
myFirstList = RandomVariate[UniformDistribution[], {10}];

mySecondList = RandomVariate[UniformDistribution[], {10}];

Take[FoldList[Plus, 0, myFirstList], {2,Length[myFirstList] + 1}] + mySecondList

• You've got an error: myFistList and correcting it produces another error. – Mr.Wizard Jan 10 '15 at 18:04
• It's a bit hard to tell; were you aiming for Accumulate[myFirstList] + mySecondList? – Mr.Wizard Jan 10 '15 at 18:06