Let algorithm A1 be defined by:
  
         = 2                            if i >= 0 and j = 0.
  a(i,j) = i + 2                        if i >= 0 and j = 1.
         = (i+2) * a(i,j-1) - a(i,j-2)  if i >= 0 and j > 1.
          
  Let algorithm A2 be defined by:
  
  Let r1 and r2 be the roots of x + 1/x = k, for k an integer.
Note that r1 + r2 = k, and r1 * r2 = 1.

  Define f(k,n) = r1^n + r2^n, for integers k >= 1 and n >= 0.

  Theorem.  a(i,j) = f(i+2,j) for i,j >= 0.
  
  Proof.  The proof shows that for a given value of i, the
  sequences 
  
    a(i,0), a(i,1), . . . , a(i,j), . . . and
    f(i+2,0), f(i+2,1), . . . , f(i+2,j), . . . and
   
are identical. Cases 1 and 2 establish the basis. Case 3 
is the induction step on j.
 
  Case 1.  j = 0:  f(i+2,0) = 2 = a(i,0).
  
  Case 2.  j = 1:  f(i+2,1) = r1 + r2 = k = i + 2 = a(i,1).
  
  Case 3.  j > 1.  Assume that a(i,m) = f(i+2,m) for 0 <= m < j.
  
  Begin with a tautology of the form (a+b)*(c+d) = a*c + b*d + b*c + a*d.
  
  (r1 + 1/r1) * (r1^(j-1) + 1/r1^(j-1)) 
    = r1^j + 1/r1^j + r1^(j-2) + 1/r1^(j-2)
      
  Since r2 = 1/r1, we have

  (r1 + r2) * (r1^(j-1) + r2^(j-1))
    = r1^j + r2^j + r1^(j-2) + r2^(j-2)
    
but this is (in general)
    
  k * f(k,j-1) = f(k,j) + f(k,j-2) or (in this specific case)
  
  (i+2) * f(i+2,j-1) = f(i+2,j) + f(i+2,j-2).
    
  Hence f(i+2,j) = (i+2) * f(i+2,j-1) - f(i+2,j-2)
  
which, by the induction hypothesis, is

  (i+2) * a(i,j-1) - a(i,j-2) = a(i,j).  
  
                               Joseph Kirtland
                               Marist College
                               Poughkeepsie, NY
                               March 12, 2018