1. ## Recurrence relation

I've been given the following recurrence realtion:
$\displaystyle a_n_+_1 = a_n_-_1 + a_n_-_3  *a_n_-_4$
How many starting values are needed to be able to calculate the number series that solves the recurrence relation.

The solution I've been given tells me I need 5 numbers, $\displaystyle a_n$ to $\displaystyle a_n_-_4$
of which 2 are not used in the above equation but needed to solve $\displaystyle a_n_+_2$

I dont really understand how they arrive at this or why $\displaystyle a_n_+_2$ even is needed to be solved here.

2. ## Re: Recurrence relation

Originally Posted by dipsy34
I've been given the following recurrence realtion:
$\displaystyle a_n_+_1 = a_n_-_1 + a_n_-_3  *a_n_-_4$
How many starting values are needed to be able to calculate the number series that solves the recurrence relation.

The solution I've been given tells me I need 5 numbers, $\displaystyle a_n$ to $\displaystyle a_n_-_4$
of which 2 are not used in the above equation but needed to solve $\displaystyle a_n_+_2$
You need to know $\displaystyle a_0,~a_1,~a_2,~a_3,~\&~a_4$.
That is five values. Now we can find $\displaystyle a_n$ for $\displaystyle n\ge 5$.

3. ## Re: Recurrence relation

Write numbers from 0 to, say, 10 in a row. The minimum value for n in the equation is 4 because there is an index n - 4. So, starting from n = 4 calculate the indices occurring in the right-hand side of the equation, i.e., n - 1, n - 3 and n - 4. If any of these numbers are not circled yet (and initially none of the numbers from 0 to 10 are circled), draw a circle around them and also write that number in a separate place. Finally, for the same value of n draw a circle around n + 1 (no need to write n + 1 separately). The newly circled numbers have to be provided to start the computation. Continue doing this for n = 5, 6, etc., and in the end see which numbers you have written in that separate place.

4. ## Re: Recurrence relation

Originally Posted by emakarov
Write numbers from 0 to, say, 10 in a row. The minimum value for n in the equation is 4 because there is an index n - 4. So, starting from n = 4 calculate the indices occurring in the right-hand side of the equation, i.e., n - 1, n - 3 and n - 4. If any of these numbers are not circled yet (and initially none of the numbers from 0 to 10 are circled), draw a circle around them and also write that number in a separate place. Finally, for the same value of n draw a circle around n + 1 (no need to write n + 1 separately). The newly circled numbers have to be provided to start the computation. Continue doing this for n = 5, 6, etc., and in the end see which numbers you have written in that separate place.
Nifty little trick, many thanks!Easy to get an answer and to prove with induction.

5. ## Re: Recurrence relation

Just to add another tip here, though obscure: you only need one base value if you assume that the addition and multiplication are undefined when neither operand is present (in which case it is treated as "blank" in the same context as the non-existent variables), and when one operand is present but not the other, the remaining operand is unity for that function. The unity for multiplication is 1. The unity for addition is 0.

Example (where "dne" means "does not exist"):
$\displaystyle a_0 = 1$ (the only given...can start at any positive number, and the function will be increasing)
$\displaystyle a_1 = a_0 + dne * dne = a_0 + dne = a_0 + 0 = 1.$
$\displaystyle a_2 = a_1 + dne * dne = a_1 + dne = a_1 + 0 = 1.$
$\displaystyle a_3 = a_2 + a_0 * dne = a_2 + a_0 * 1 = a_2 + a_0 = 2.$
$\displaystyle a_4 = a_3 + a_1 * a_0 = a_3 + 1 = 3.$
$\displaystyle a_5 = a_4 + a_2 * a_1 = a_4 + 1 = 4.$
$\displaystyle a_6 = a_5 + a_3 * a_2 = a_5 + 2 = 6.$

...and so on. Note that the "dne" sticks around until you get past the first four cases.

There are situations where this is a particularly useful approach, though I wouldn't normally assume this behavior is intended without being told it's allowed (here). This is how you handle empty sums and products in the general case, though.