Is Linear Prediction ever exact? I'm just learning about linear prediction and was wondering whether or not there are any signals that would produce no error if run through a linear prediction algorithm. I was thinking (maybe naively) that if we have a linear signal (one that changes linearly with time) that we should be able to linearly predict this with no error. Is my intuition on this correct? Are there any other signals that are like this?



First of all, thanks so much for the replies! Secondly, I'm glad my intuition was correct, but I was having doubts in the first place because I couldn't exactly predict future samples of my signal no matter what my input signal was. For example, here's an image of me trying to get the linear prediction coefficients using 'lpc' function in Matlab. 



I've tried this for several of the types of signals suggested above, and didn't get the correct coefficients for any of them. Why does this happen? I doubt the 'lpc' function is incorrect so it just must be doing something different than what I thought it was doing.
Theoretically, yes. So you can for instance predict values taken by polynomials, with the following initial patterns:


degree $0$: $\hat{S}[n] = {S}[n-1]$;
degree $1$: $\hat{S}[n] = 2{S}[n-1]-{S}[n-2]$;
degree $2$: $\hat{S}[n] = 3{S}[n-1]-3{S}[n-2]+{S}[n-3]$;
degree $3$: $\hat{S}[n] = 4{S}[n-1]-6{S}[n-2]+4{S}[n-3]-{S}[n-4]$;


and so on. You can recognize binomial coefficients. 

There are similar  linear relations for other signals when sampling conditions are met, and for different cost functions. I am happy to dig into old stuff here. In a 1927, G.  Udny Yule (the same as in autoregressive modeling known under Yule-Walker), On a Method of Investigating Periodicities in Disturbed Series, with Special Reference to Wolfer's Sunspot Numbers,  gave the following trigonometric recurrence relation  (using the same notations), for:

$$\begin{align} 
u_0 &amp; =&amp; A \sin\left({2\pi\frac{t+\tau}{T}}\right)\\
u_1 &amp; =&amp; A \sin\left({2\pi\frac{t+\tau+h}{T}}\right)\\
u_2 &amp; =&amp; A \sin\left({2\pi\frac{t+\tau+2h}{T}}\right)\end{align}
 $$
then 
$$ u_2 = (2-\mu)u_1-u_0$$
with $\mu = 4 \sin^2 \pi\frac{h}{T}$. One can notice that, when $\mu =0$, one recognizes the linear extrapolation: $ u_2 = 2u_1-u_0$.

I would suggest: 


The Theory of Linear Prediction by P. P. Vaidyanathan, or 
chapter 13.6 Linear Prediction and Linear Predictive Coding  in Numerical Recipes.


In practice, the exactness is limited by the data precision (in time and amplitude), for instance by finite-word quantization (rounding errors, floating point operations) and jitter, in time.