# Solve recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1)

$T(N) = N + T(N-3)$

This is what I got so far

$$\begin{align}&= T(N-6) + (N-3)+N\\ &= T(N-9) + (N-6) + (N-3)+N \\ &= T(N-12) + (N-9) + (N-6) + (N-3)+ N\end{align}$$

I think I should use $(n^2 + n) / 2$.

im not sure if im doing it right or not!

Thanks :)

-

1
– user53153 Feb 6 at 5:12
$N,N-3,N-6,N-9,\ldots$ form an arithmetic progression. Use the formula for the sum of an AP – dexter04 Feb 6 at 5:12

## 1 Answer

Note: we generally express functions of integer arguments with subscripts, i.e. $T_n$ rather than $T(n)$.

This is a constant-coefficient difference equation. To specify the solution, you need three initial conditions, say, $T_1$, $T_2$, and $T_3$. In general, the solution takes the form

$$T_n = T_n^{(H)} + T_n^{(I)}$$

where $T_n^{(H)}$ is a homogeneous solution satisfying

$$T_n^{(H)} - T_{n-3}^{(H)} = 0$$

and the initial conditions, and T_n^{(I)}\$ is an inhomogeneous solution satisfying

$$T_n^{(I)} - T_{n-3}^{(I)} = n$$

The homogeneous piece takes the form $a r^n$ for some (potentially complex) value of $r$. When we plug this into the homogeneous equation, we get

$$r^3-1=0$$

which has solutions $r=1$, $r=\omega = e^{i 2 \pi/3}$, and $r=\omega^2 = e^{i 4 \pi/3}$. The homgeneous solution is then a linear combination of the solutions corresponding to these roots, i.e.,

$$T_n^{(H)} = A + B \omega^n + C \omega^{2 n}$$

where the constants $A$, $B$, and $C$ are determined by the initial conditions.

The inhomogeneous solution is determined by the factor of $n$, and because of the nature of the equation (a difference), we guess it takes the form $T_n^{(I)} = P n + Q n^2$. Plugging this into the equation, we see that

$$3 P + (6 n-9) Q = n$$

which implies that $Q = 1/6$ and $P = 1/2$. The general solution to the equation is then

$$T_n = A + B \omega^n + C \omega^{2 n} + \frac{1}{6} n (n+3)$$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8884806036949158, "perplexity_flag": "head"}