1. Recurrence relation

I've been given the following recurrence realtion:
$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, $a_n$ to $a_n_-_4$
of which 2 are not used in the above equation but needed to solve $a_n_+_2$

I dont really understand how they arrive at this or why $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:
$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, $a_n$ to $a_n_-_4$
of which 2 are not used in the above equation but needed to solve $a_n_+_2$
You need to know $a_0,~a_1,~a_2,~a_3,~\&~a_4$.
That is five values. Now we can find $a_n$ for $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"):
$a_0 = 1$ (the only given...can start at any positive number, and the function will be increasing)
$a_1 = a_0 + dne * dne = a_0 + dne = a_0 + 0 = 1.$
$a_2 = a_1 + dne * dne = a_1 + dne = a_1 + 0 = 1.$
$a_3 = a_2 + a_0 * dne = a_2 + a_0 * 1 = a_2 + a_0 = 2.$
$a_4 = a_3 + a_1 * a_0 = a_3 + 1 = 3.$
$a_5 = a_4 + a_2 * a_1 = a_4 + 1 = 4.$
$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.