CSC 133 Discrete Structures Quiz Chapter 8.1-2a Spring 2001

1. Given the recurrence relation a_k = 5a_{k - 1} + 1, kÎ Z, k ³ 3, a₂ = 1.

1. Write out the next four terms of this sequence in expanded form, (do not add the numbers up, just simplify each term).
   a₂ = 1,
   a₃ =
   
   a₄ = 
   
   a₅ = 
   
   
2. What is an explicit formula for this recurrence relation given that it is either an arithmetic or geometric series satisfying some perturbation of n(n + 1) / 2 or (rⁿ⁺¹ - 1)/(r - 1)?
   
   a_n =
    
3. Show that your formula works for a₆ by solving for a₆ recursively then explicitly. (show your work)
   Recursively, a₆ = 
   
   
   Explicitly, a₆ = 
   

2. Given the recurrence a_k = (1/2)(a_k - 1 + r / a_k - 1), kÎ Z, k ³ 1, one can find the square root of any positive real number r by making an initial guess as to what a_k - 1 might be. Say we want to find the square root of 12 and we make an initial guess of a₀ = 3. (Known as the Newton-Raphson iterative method.)