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!
 A: 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.
