From Recurrence relation to closed form

Question

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.

Answer 1

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 $$

Answer 2

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

Answer 3

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.