# Programmatically Solve Recurrency equations in Closed form?

$$\begin{cases} V(k)=0 \text{ as } k < 1 \\ V(k+1) -V(k) = \left(\frac{1}{2}\right) \left(V(k) - V(k-1) \right) \text{ as } k \in [1,9] \\ V(k+1) = V(k) \text{ as } k >9 \end{cases}$$

I have got

$$V(10) - V(9) = (\frac{1}{2} (V(9) - V(8))$$ so $$1 = \left(\frac{3}{2}\right) V(9) - \frac{1}{2} V(8)$$ and $$V(9) = \frac{3}{2} V(8) - \frac{1}{2} V(7)$$ ... $$V(2) - V(1) = (\frac{1}{2} (V(1) - V(0))$$ so $$V(2) = \frac{3}{2} V(1)$$

now I got

$$V(3) = \frac{7}{6} V(2)$$

n  | V
---------
0  | 0
1  | V(1)
2  | 3/2 *V(1)
3  | 7/4 *V(1)
4  | 15/8 *V(1)
5 ...
6
7
8
9  ..
10 | 1


without calculating this by hands like this, is there some easy way to programmatically do this?

-
Where you have 7/6 you probably mean 7/4 – Henry Oct 9 '11 at 0:45
@Henry: thank you,fixed. – hhh Oct 9 '11 at 6:43
You can take a look at this answer. – Pierre-Yves Gaillard Oct 9 '11 at 6:48

Assuming $k$ must be an integer, are you looking for something similar to this?

• $V(0) = 0 \text{ for } k \lt 1$

• $V(k)=\dfrac{2^n-1}{2^{n-1}} V(1) \text{ for } k \in [1,9]$

• $V(k) = \dfrac{511}{256} V(1) \text{ for } k \gt 9$

-

Your recurrence (below $k=10$) is $V(k+1)=\frac{3}{2}V(k)-\frac{1}{2}V(k-1)$. The standard approach for linear homogeneous recurrences like this is to assume the solutions are of the form $ar^k$. If you substitute that into your recurrence, the $a$'s divide out and you are left with $2r^2=3r-1$ Solving this gives $r=1,\frac{1}{2}$ so the general solution is $V(k)=a+b(\frac{1}{2})^k$ and you need two initial conditions to get $a$ and $b$. In your case, you have $V(0)=0$ and we will let $V(1)=c$. Then $a+b=0, a+\frac{b}{2}=c$, leading to $V(k)=2c(1-\frac{1}{2^{k}})$. Then you need to impose the fact that nothing changes after $k=9$. A discussion is at Wikipedia and there are texts on linear recurrence relations.

-