title: Using matrices to find the number of different ways to write n as the sum of 1, 3, and 4?
body: <p>This is a question given in this presentation. <a href="https://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf" rel="nofollow noreferrer">Dynamic Programming</a></p>
  
  <p>now i have implemented the algorithm using recursion and it works fine for small values. But when n is greater than 30 it becomes really slow.The presentation mentions that for  large values of n one should consider something similar to
  <a href="https://math.stackexchange.com/questions/784710/how-to-prove-fibonacci-sequence-with-matrices">the matrix form of Fibonacci numbers</a> .I am having trouble undestanding how to use the matrix form of Fibonacci numbers to come up with a solution.Can some one give me some hints or pseudocode</p>
  
  <p>Thanks</p>