# Recurrence Relation Homework Struggles

Here's the question: Solve the recurrence by obtaining a $\theta$ bound for $T(n)$ given that $T(1) = \theta(1)$.

$T(n) = n + T(n-3).$

Attempted Solution:

\begin{align*} T(n) &= T(n-6) + (n-3) + n \\ &= T(n-9) + (n-6) + (n-3) + n \\ &= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + \cdots + n]\\ &= T(1) + [0 + 3 + 6 + \cdots + n]\\ &= \theta(1) = 3[1 + 2 + 3 + \cdots + n/3]\\ &= \theta(1) + \frac{(n/3)(n/3 + 1)}{2}\\ &= \theta(1) + \frac{n^2+3n}{6}. \end{align*} When I double check to see if the solution fits the recurrence, it doesn't work. I can solve these fairly easily when it involves the previous term, but this $T(n-3)$ is throwing me off. Been at this one for a while now; please help T__T

-
This seems to be written in the language of computer science rather than mathematics. Can someone explain to me what a $\theta$ bound is, and what $T(1) = \theta(1)$ means here? – Pete L. Clark Jan 29 '11 at 23:34
Also, to my eye the problem is ill-posed, since the recurrence does not define $T$ for all $n$. – Pete L. Clark Jan 29 '11 at 23:36
@Pete: Yes, this notation is common in computer science (but historically, it derives from notation created for number theory). Also, yes, not all base cases are defined. The culture for HW problems like this is to really assume constant values for any missing base cases. – Mitch Jan 29 '11 at 23:57
@Mitch: okay, but what does it mean? Also, filling in any finite number of values is not going to be sufficient: the recursion still won't define a function on all positive integers. – Pete L. Clark Jan 30 '11 at 1:21

From the initial condition on $T(1)$ and the recurrence relation, there is no way to estimate $T(n)$ unless $n=3k+1$ for some $k\ge0$.

For every $k\ge0$, let $U(k)=T(3k+1)$. Then $U(k)=3k+1+U(k-1)$, hence $U(k)=(3k+1)+(3k-2)+\cdots+4+U(0)$, that is, $T(3k+1)=\frac12k(3k+5)+\Theta(1)$.

-
• if you have no clue about the general manipulation of the formula, try some specifics. For example, let $T(0)=T(1)=T(2)=0$, then $T(3) =$ ??, $T(6) =$ ??, etc. and then guess a solution.
• you have no problem with recurrences with T(n-1). One trick with recurrences is to convert the weird inscrutable ones (like for you this $T(n-3)$) -somehow- to $T(n-1)$. The previous bullet point will help with that...create a new function to solve for $S(n)$ where $S(n) = T(3n)$ (you might also have to do it for $T(3n+1)$ and $T(3n+2)$ ). This is called 'change of variables'.

This might seem like more work than it's worth, just to solve this problem, but you've already spent time trying to solve it without getting anywhere so might as well try the extra work.

Actually...you seem to have implicitly done these steps in your attempted solution. Have you checked your steps? What is $n/3(n/3+1)$?

-
The $3$ dropped out for some reason so it should be $3 \cdot [n/3(n/3 + 1)/2]$ resulting in the same final solution presented. – Jason Jan 31 '11 at 0:28
I'm upvoting this because I was going to suggest the change of variables. – Michael Lugo Jan 31 '11 at 0:30

The reasoning given at StackOverflow works (assuming $n \equiv 1 \pmod 3$) except that there was a slight error in the calculation of the summation $4 + 7 + \ldots + n/3$, which is equal to $(4 + n)(n - 1)/6$ and not $(4 + n)(n - 1)/3$. Letting $m = (n-1)/3$, you can express this summation as follows:

$[\sum_{i = 1}^{m}(3i + 1)]$

= $m + \sum_{i=1}^{m}3i$

= $m + 3 \cdot \sum_{i=1}^{m}i$

= $m + 3[ m \cdot (m + 1)/2]$

= $m + (3m^2 + 3m)/2$

= $(3m^2 + 5m)/2$

= $[3((n-1)/3)^2 + 5((n - 1)/3)]/2$

= $(n^2 - 2n + 1 + 5n - 5)/6$

= $(n^2 + 3n - 4)/6$

= $(n + 4)(n - 1)/6$

= $(n-1)/3 + [(n-1)^2 + 3(n-1)]/6$

= $(5(n-1) + (n-1)^2)/6$

= $(5n - 5 + n^2 - 2n + 1)/6$

= $(n^2 + 3n - 4)/6$

= $(n + 4)(n-1)/6$

...so $T(n) = \Theta(1) + (n+4)(n-1)/6$, as you pointed out on StackOverflow.

-
Why are you assuming $n \equiv 1 \pmod 3$? – Pete L. Clark Jan 31 '11 at 2:41
@Pete: This was so I justified the case mentioned in the answer on StackOverflow where the answerer says the sum becomes "$T(1) + [4 + 7 + \ldots + n]$", but the final solution I gave to the recurrence relation can be verified to work for all $n \in \mathbb{N}$ by considering the other two congruences. – Jason Jan 31 '11 at 4:05
@Pete: the assumption for $1 \bmod 3$ is because of the missing two other base cases. – Mitch Jan 31 '11 at 18:24
@Mitch: I thought we had established that all three base cases are missing but that one need not know their values to answer the question. Whatever $T(1) = \Theta(1)$ is supposed to mean, it is not specifying the value of $T$ at $1$, right? – Pete L. Clark Jan 31 '11 at 19:27
@Pete: Sorry for reintroducing doubt. The only base case like thing in the original question is $T(1) = \Theta(1)$, it does not mention $T(2)$ or $T(3)$. Since the recurrence goes back 3, these two are needed for $T(3k+2)$ and $T(3k)$. To read between the lines, equivalently to specify this appropriately for TCS culture, the question should state either the two extra base cases or say instead $T(\Theta(1)) = \Theta(1)$, meaning -all- base cases are constants (which of course, they must be anyway, or you'd be talking about a family of functions). Which is to say... – Mitch Jan 31 '11 at 20:31