# From Recurrence relation to closed form

How do i get from the following Recurrence Relation

$T(0) = 0$;
$T(1) = 7$;
$T(n) = T(n-2) +7$ for $n$ $\ge$ 2

to the closed form? I know that the solution is

$\frac{7n}{2}-\frac{7(-1)^n}{4}+\frac{7}{4}$

But my problem is getting there, for other recurrence relations i can use the arithmetic series or geometric series to get the closed form but i don't know how I could use any of them here, I tried to insert some small integers for n and got the Sequence

$0, 7, 7, 14, 14, 21, 21$

$T(2) = 7, T(3) = 14, T(4) = 14, T(5) = 21, T(6) = 21$

but that doesn't help me at all to be honest, is there any tip or trick to get easier/faster to the closed form? Any help is appreciated.

First, $T(0)=0$, $T(2)=7$, $T(4)=14$, and so on: it shouldn't be difficult to prove by induction that $T(2n)=7n$.

Next, $T(1)=7$, $T(3)=14$, and so on; by induction, $T(2n+1)=7(n+1)$.

If you want a “true” closed form, it's easier to consider $S(n)=T(n)/7$, so $$S(n)=\begin{cases} \dfrac{n}{2} & \text{n even} \\[6px] \dfrac{n+1}{2} & \text{n odd} \end{cases}$$ Note that, for $n$ even, $n/2=\lceil n/2\rceil$; for $n$ odd, $(n+1)/2=\lceil n/2\rceil$; so you can write $$S(n)=\left\lceil\frac{n}{2}\right\rceil$$ and therefore $$T(n)=7\left\lceil\frac{n}{2}\right\rceil$$

• thank you, that actually helped me a lot to understand it, i didn't think of "seperate" the recurrence relation in odd/even and do prove it by induction separately(always tried to do it in one induction), your solution T(n)=7⌈n2⌉ looks also so much easier than mine. Thanks! – fleksz Jul 12 '18 at 17:56

The standard generating function approach yields $$GF=\frac{7x(1+x)}{1-2x^2+x^4}$$ which can be manipulated into $$GF=\frac{7x}{(1-x)^2(1+x)}$$ Applying the theory of partial fractions gives $$GF=-\frac{7}{4(1+x)}-\frac{7}{4(1-x)}+\frac{7}{2(1-x)^2}$$ which are all recognizable contributions to a formula for the $$n$$th term $$-\frac{7}{4}(-1)^n-\frac{7}{4}n+\frac{7}{2}(n+1)$$ which, with some minor tidying up, is the answer claimed in the question

You have the following:

$$T_n - T_{n-2} = 7 = T_{n-2} - T_{n-4} \implies T_n - 2T_{n-2} + T_{n-4} = 0$$

The characteristic equation is $$x^4 - 2x^2 + 1 = 0$$. This factors as $$(x-1)^2(x+1)^2$$. Hence you get that:

$$T_n = a\cdot 1^n + b \cdot n \cdot 1^n + c \cdot (-1)^n + d \cdot n \cdot (-1)^n$$

Use the initial values $$T_0 = 0 : T_1 = T_2 = 7 : T_3 = 14$$ to find the values $$a,b,c,d$$ and hence the closed form.