# When is a recurrence relation linear

In http://www.cs.fsu.edu/~lacher/courses/COT5405/spring07/notes2.html, it says that $T(n) = aT(n/b) + f(n)$ is nonlinear recurrence.

But I think it is linear because $T(n)$ is linear in $T(n/b)$.

So I was wondering how a linear recurrence is defined?

Thanks and regards!

-
If $T(n)$ were recursively expressed in terms of $T(n-1),T(n-2),\dots$, then it would be linear. –  Guess who it is. Apr 25 '11 at 1:32
It's already nonlinear because of the $f(n)$ term. –  Qiaochu Yuan Apr 25 '11 at 3:16
@Qiaochu: The $f(n)$ term makes it non-homogeneous. –  Mitch Apr 25 '11 at 4:04
@Qiaochu, are you taking the Humpty-Dumpty approach to language, where a word means what you want it to mean - it's just a question of who's to be master? $y=3x+4$ is a linear equation, $y'=y+x$ is a linear DE, and $T(n)=T(n-1)+n$ is a linear recurrence, whether you would say so or not. –  Gerry Myerson Apr 25 '11 at 11:59
@Qiaochu: it's not the function itself implied by the recurrence that is linear, it is the operations on the function that are linear. See my addendum and the link..OK I'll give it away...it's the same terminology as for ordinary differential equations. –  Mitch Apr 26 '11 at 1:46

A linear recurrence relation does not have terms with more than one recurrent factor.

That is,

$$T(n) = T(n-1)T(n-2) + T(n-3)$$

is not linear because of the term $T(n-1)T(n-2)$, but

$$T(n) = T(n/2) + T(n/3) + 1$$

is linear.

A recurrence is of finite order is one where the 'number of steps back that one takes' are specified by a constant (which is finite). So

$$T(n) = T(n-1) +1$$

is of finite order but

$$T(n) = T(n/2) +1$$

is not.

A recurrence has constant coefficients if, naturally, all the coefficients are constants. So

$$T(n) = n(T(n-1) + T(n-2))$$

has non-constant coefficients but

$$T(n) = 2 T(n/2)T(n-1) + n^2$$

has constant coefficients.

A recurrence is homogeneous if all terms have a factor that is recurrent. So

$$T(n) = n^2 T(n-1)T(n-2) + T(n-3)^3$$

is homogeneous but

$$T(n) = T(n-1) + 1$$

has not homogeneous.

So in my language, $T(n)=aT(n/b)+f(n)$ is linear but not of finite order and not homogeneous (and would be orthogonally called a divide and conquer recurrence).

Those are the definitions that I follow (and learned from somewhere - texts on discrete mathematics - I think Rosen, Liu, Tucker). If those are your notes for a class you are taking, I'd go with that definition while you are taking the class, and be very aware that other texts use different meanings.

As an addendum, these definitions are useful, whatever their mismatch with what you expect, whether they match the terminology used in other ...oh... duh... the terminology for recurrences is based on that of linear differential equations. Pretty much the same stuff.

-
Thanks! That webpage of the class was just found by me via google. I was wondering which book by Tucker you mentioned? –  Tim Apr 25 '11 at 3:06
Alan Tucker, Applied Combinatorics, Rosen; Kenneth Rosen, Discrete Mathematics and its Applications; Liu, Intro to Discrete Math (very old, probably not in there). Googling, I found it hard to support 'finite order' directly, but people seem to be using it as I defined. –  Mitch Apr 25 '11 at 3:15