title: generating matrix for a recurrence relation
body: <blockquote>
    <p>Answered on Math.SE, <a href="https://math.stackexchange.com/questions/124178/generating-matrix-for-a-recurrence-relation">generating matrix for a recurrence relation</a></p>
  </blockquote>
  
  <p>for the recurrence <code>f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)</code> , how can one get the generating matrix so that it can be solved by matrix exponentiation?</p>
  
  <p>For <code>f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)</code> the corresponding generating matrix is: </p>
  
  <pre><code>| a  0  c |   |  f(n)  |   | f(n+1) |
  | 1  0  0 | x | f(n-1) | = |  f(n)  |
  | 0  1  0 |   | f(n-2) |   | f(n-1) |
  </code></pre>
  
  <p>so how to get the same for required recurrence?
  Also what should be the procedure for any recurrence which may be of the form :</p>
  
  <p><code>f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k)</code> ?</p>
  
  <p>Thanks.</p>