# Thread: How to write this down - basic

1. ## How to write this down - basic

Hi,

i need little help. This is a problem from computer science and what i have is an array A every array has a position and every position is indexed. Furthermore what i have is a case where for let say k=3 i wish to sum the following:

A[i] + A[i + A[i]] + A [i + A[i] + A[i + A[i]]]

Now i am not a mathematician so please do not laugh. What i don't know is how to write this down nicely.
what confuses me is this recursion. so A[i] is a value of the array on position i , A[i+A[i]] is a value on that position but the position at which i am checking for value is dependent on the sum of previous positions. So it would go something like this :

$\sum^{k}_{s=0} \mbox{A[}i+\sum^{s}_{p=0}\mbox{what goes here!!]}$ i cannot just write down $\mbox{A_{b}}$ because it is not obvious what that is

thnx

2. ## Re: How to write this down - basic

Originally Posted by baxy77bax
This is a problem from computer science and what i have is an array A every array has a position and every position is indexed. Furthermore what i have is a case where for let say k=3 i wish to sum the following:

A[i] + A[i + A[i]] + A [i + A[i] + A[i + A[i]]]

Now i am not a mathematician so please do not laugh. What i don't know is how to write this down nicely.
How do you need to write it: in English, in C, in pseudocode, as a math formula using Σ, as a recurrence relation, etc.?

3. ## Re: How to write this down - basic

Yes i did not mention that as a math formula using \sum . it th same way i started it in the initial post:

$\sum^{k}_{s=0} \mbox{A[}i+\sum^{s}_{p=0}\mbox{what goes here!!]}$

PS

isn't that the same as saying "recurrence relation"??

4. ## Re: How to write this down - basic

Originally Posted by baxy77bax
A[i] + A[i + A[i]] + A [i + A[i] + A[i + A[i]]]
Could you write two more terms (i.e., a sum of 5 terms)? I am not sure I grasp the rule.

5. ## Re: How to write this down - basic

A[i]
+ A[i + A[i]]
+ A[i + A[i] + A[i + A[i]]]
+ A[i + A[i] + A[i + A[i]] + A[i + A[i] + A[i + A[i]]]]
+ A[i + A[i] + A[i + A[i]] + A[i + A[i] + A[i + A[i]]] + A[i + A[i] + A[i + A[i]] + A[i + A[i] + A[i + A[i]]]]]

6. ## Re: How to write this down - basic

I think it's difficult to write it as an explicit sum. It is convenient to make an auxiliary recursive definition (define a recurrence relation):

$a_1 = i$
$a_{n+1} = a_n + A[a_n]$

Then the expression is $\sum_{n=1}^k A[a_n]$.

7. ## Re: How to write this down - basic

ok that what i was looking for , because i was trying to express it as a sum and could not. so all i needed is one more conformation that it is difficult enough not to wast time on it.

thank you