Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$

I tried solving it using the forward iteration. $$\begin{align} T(3) &= 1 + 1/2\\ T(4) &= 1 + 1/2\\ T(5) &= 1 + 1/2\\ T(6) &= 1 + 1/2 + 1/2 = 2\\ T(7) &= 1 + 1/2 + 1/2 = 2\\ T(8) &= 1 + 1/2 + 1/2 = 2\\ T(9) &= 2 + 1/2 \end{align}$$

I couldnt find any sequence here. can anyone help !!

share|improve this question
3  
You really could not see a pattern? –  Mariano Suárez-Alvarez Feb 12 '13 at 6:12
add comment

4 Answers

The crucial observation is that the sequence occurs in blocks of 3, so for each $n$ we need to find out "which block of 3 is $n$ in". So using $\lfloor n/3\rfloor$ or $\lceil n/3\rceil$ would be good.

Observe the pattern: $$\begin{array}{c} n & T(n) & \lceil n/3\rceil\\\hline 0 & 2/2 & 1\\\hline 1 & 2/2 & 1\\\hline 2 & 2/2 & 1\\\hline 3 & 3/2 & 2\\\hline 4 & 3/2 & 2\\\hline 5 & 3/2 & 2\\\hline 6 & 4/2 & 3\\\hline 7 & 4/2 & 3\\\hline 8 & 4/2 & 3\\\hline \end{array}$$

share|improve this answer
add comment

It’s just three copies of a single recurrence interlaced with one another. The three copies are the sequences $\langle T(3n):n\in\Bbb N\rangle$, $\langle T(3n+1):n\in\Bbb N\rangle$, and $\langle T(3n+2):n\in\Bbb N\rangle$. Each looks just like the sequence defined by $S(0)=1$ and $S(n)=S(n-1)+\frac12$ for $n\ge 1$, which pretty clearly has the closed form $S(n)=\frac{n}2$.

How does $T(n)$ compare with $S\left(\left\lfloor\frac{n}3\right\rfloor\right)$?

share|improve this answer
add comment

I believe this is the right answer:

$$ \\ T(n) = T(n - 3) + \frac{1}{2} \\ T(n) = T(n - 6) + \frac{1}{2} + \frac{1}{2} = T(n - 6) + \frac{2}{2} \\ T(n) = T(n - 9) + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = T(n - 9) + \frac{3}{2} \\ T(n) = T(n - 12) + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = T(n - 12) + \frac{4}{2} \\ ... \\ T(n) = T(n - k) + \frac{k}{3} \times \frac{1}{2} \\ \text{When }n - k = 0 \Rightarrow n = k \\ T(n) = T(0) + \frac{n}{3} \times \frac{1}{2} \\ \text{Hence, } T(n)\ \epsilon \ O(n) $$

share|improve this answer
    
Why come back to this? Especially to pretend that $T(n)$ and $T(0)$ are related when $n$ is not a multiple of $3$ (they are not). –  Did Mar 9 at 16:05
add comment

The generating function is $$g(x)=\sum_{n\ge 0}T(n)x^n = \frac{2-x^3}{2(1+x+x^2)(1-x)^2}$$, which has the partial fraction representation $$g = \frac{2}{3(1-x)} + \frac{1}{6(1-x)^2}+\frac{x+1}{6(1+x+x^2)}$$. The first term contributes $$\frac{2}{3}(1+x+x^2+x^3+\ldots)$$, equivalent to $T(n)=2/3$ the second term contributes $$\frac{1}{6}(1+2x+3x^2+4x^3+\ldots)$$ equivalent to $T(n) = (n+1)/6$, and the third term contributes $$\frac{1}{6}(1-x^2+x^3-x^5+x^6-\ldots)$$ equivalent to $T(n) = 1/6, 0, -1/6$ depending on $n\mod 3$ being 0 or 1 or 2. $$T(n) = \frac{2}{3}+\frac{n+1}{6}+\left\{\begin{array}{ll} 1/6,& n \mod 3=0\\ 0,& n \mod 3=1 \\ -1/6,&n \mod 3 =2\end{array}\right.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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