We consider the recurrence equation (R) x_n+1 = 13x_n 4x_n1 (for all n 1),

when x0, x1 are given. 1.1 Prove that if x₀=1 and x₁=1/3, then x_n=3ⁿ for all n 0.

1.2 Compute 3ⁿ for n = 1 through 50. Directly use the formula 3ⁿ itself (in a for-loop, in Python or C, etc.). Use double precision (not more, not less). Give the resulting 50 numbers 3ⁿ, together with the corresponding n.

1.3 Write a small program (in Python or C, etc.) to compute x_n by using the recurrence equation (R) above, for n = 1 through 50. Use double precision (not more, not less). Give the resulting 50 numbers, together with the corresponding n.

1.4 Comparing 1.2 and 1.3, what is strange about the numbers near the end in 1.3 ? 1.5 Use the recurrence equation (R), but now with x₀ = 1 and x₁ = 1/3 10⁴, to compute x_n for n = 1 through 50 (in double precision). Give the resulting 50 numbers with the corresponding n, and your (short) program.

1.6 Assume x₀ = 1,x₁ = 1/3 10⁴. Find two numbers A and B such that for all n {0,1}: x_n = 3ⁿA+4ⁿB.

1.7 For the values of A and B found in 1.6, prove that the sequence x_n = 3ⁿA+4ⁿB satisfies the recurrence equation for all n 0.

1.8 In light of 1.7, explain the observations in 1.4. (Think in terms of amplification and propagation of numerical imprecision, or errors. )