title: Sum of sum of i^k using matrix exponentiation
body: <blockquote>
    <p>f(n) is defined as: f(n) = 1^k+2^k+3^k+...+n^k, so it is the sum
    of the k-th power of all natural numbers up to n.</p>
    
    <p>In this problem you are about to compute,</p>
    
    <p>f(1) + f(2) + f(3) + ... + f(n)</p>
    
    <p>1 ≤ n ≤ 123,456,789 and 0 ≤ k ≤ 321</p>
  </blockquote>
  
  <p>( Link to the original problem: <a href="http://www.spoj.com/problems/ASUMHARD/Matrix" rel="nofollow noreferrer">http://www.spoj.com/problems/ASUMHARD/Matrix</a> )</p>
  
  <p>A naive algorithm, computing each term one by one runs too slow so I thought of trying to solve a reccurence relation.</p>
  
  <p>Naive approach:</p>
  
  <pre><code>total = 0
  for i = 1 to n:
      for j = 1 to i:
          total += j^k
  return total
  </code></pre>
  
  <p>Exponentiation can be used to solve Linear Recurrence .
  I know how to solve linear recurrences like :</p>
  
  <pre><code>f(n) = f(n-k1) + f(n-k2) + ... + constant
  </code></pre>
  
  <p>But i couldn't find any information on how to solve recurrences like</p>
  
  <pre><code>f(n) = f(n-k1) + f(n-k2) + ... + n^m 
  </code></pre>
  
  <p>or</p>
  
  <pre><code>f(n) = f(n-k1) + f(n-k2) + ... + n*m
  </code></pre>
  
  <p>or</p>
  
  <pre><code>f(n) = f(n-k1) + f(n-k2) + ... + k^n
  </code></pre>
  
  <p>i.e. 
  involving an 'n' term.</p>
  
  <p>How can such recurrences be solved, or how to form the initial matrix whose power will be used to solve the recurrence? If not utilizing matrix exponentiation can someone at least describe an idea on how to approach it?</p>