[HN Gopher] Solving Recurrence Relations
       ___________________________________________________________________
        
       Solving Recurrence Relations
        
       Author : jmount
       Score  : 29 points
       Date   : 2024-05-11 18:31 UTC (1 days ago)
        
 (HTM) web link (win-vector.com)
 (TXT) w3m dump (win-vector.com)
        
       | jcla1 wrote:
       | Unfortunately the presented method only works for the most simple
       | linear recurrence relations.
       | 
       | Tangentially: look up the master theorem if you're interested in
       | at least estimating growth rates for recurrence relations that
       | crop up in computer science.
        
       | matheist wrote:
       | To my taste this is not very illuminating, it feels like the
       | answer is produced via a magic trick.
       | 
       | My personal preference for understanding linear recurrence
       | relations (and understanding where/why sqrt(5) shows up for the
       | Fibonacci sequence) is via eigenvalues and eigenvectors of a
       | corresponding linear transformation. For example:
       | [F_n  ] = [1 1] [F_n-1]       [F_n-1]   [1 0] [F_n-2]
       | 
       | and therefore                 [F_n  ] = [1 1]^n-2 [F_2] = [1
       | 1]^n-2 [1]       [F_n-1]   [1 0]     [F_1]   [1 0]     [1]
       | 
       | and therefore the nth Fibonacci number can be computed by
       | computing the (n-2)th power of the matrix [[1, 1], [1, 0]], and
       | then multiplying that matrix by the column vector [1, 1] (or any
       | other desired first terms of the sequence). The matrix power can
       | be computed by diagonalizing, and that's where the powers of the
       | golden ratio will come up (as eigenvalues of that matrix).
       | 
       | This is completely equivalent to the method in TFA, but to my
       | mind is better motivated.
        
         | fernmyth wrote:
         | Solving recurrence relations has always felt just out of reach
         | for me. But rewriting it in matrix form makes so much sense!
         | Thanks!
        
       | gballan wrote:
       | Siebert [1] is great for this stuff (z-transform). The Fibonacci
       | sequence appears in problem 7.2.
       | 
       | [1] Siebert, William McC.. Circuits, Signals, and Systems.,
       | McGraw-Hill, 1986.
        
       ___________________________________________________________________
       (page generated 2024-05-12 23:00 UTC)