1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – fleksz Jul 12 '18 at 17:56
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.