Assignment 3 Due Thursday, March 9th As always, show your work and explain your answer. 1. Consider the linear recurrence a0 = 1, a1 = 0, and for i ≥ 2, ai = 5ai−1 − 6ai−2. (a) Let f(x)...

SOL
1.
(a) We start by multiplying the recu
ence by xi and summing from i = 2 to infinity:
ai xi = 5ai-1 xi - 6ai-2 xi ∑ ai xi = ∑ 5ai-1 xi - ∑ 6ai-2 xi ∑ ai xi = 5x(∑ ai-1 xi) - 6x^2(∑ ai-2 xi)
We can rewrite the last equation as:
f(x) - a0 - a1x = 5x(f(x) - a0) - 6x^2f(x)
Simplifying and solving for f(x), we get:
f(x) = (1 - 5x)/(1 - 5x + 6x^2)
(b) To expand f(x) using partial fractions, we need to factor the denominator:
1 - 5x + 6x^2 = (2x - 1)(3x - 1)
We can then write f(x) as:
f(x) = A/(2x - 1) + B/(3x - 1)
Multiplying both sides by (2x - 1)(3x - 1), we get:
1 - 5x + 6x^2 = A(3x - 1) + B(2x - 1)
Substituting x = 1/2 and x = 1/3, we can solve for A and B:
A = 4, B = -3
Therefore, we can write f(x) as:
f(x) = 4/(2x - 1) - 3/(3x - 1)
To determine the coefficient an, we need to expand f(x) in a power series:
f(x) = 4/(2x - 1) - 3/(3x - 1) = 4/2 ∑ (x/2)^n - 3/3 ∑ (x/3)^n = 2 ∑ (x/2)^n - ∑ (x/3)^n
Using the formula for the coefficient of xn in a power series, we can see that:
an = 2^(n+1) - 3^n
for all n ≥ 0.
2.
(a) To express f(x) as a sum of two terms, we need to factor the denominator first:
x^2 - x + 3 = (x - (1+2i))(x - (1-2i))
Then we can write:
f(x) = A/(x - (1+2i)) + B/(x - (1-2i))
where A and B are constants to be determined. We can find A and B by multiplying both sides by the denominators and simplifying:
1 = A(x - (1-2i)) + B(x - (1+2i)) 1 = (A+B)x - (A(1-2i) + B(1+2i))
Equating the coefficients of x and the constant term, we get:
A + B = 0 A(1-2i) + B(1+2i) = 1
Solving for A and B, we get:
A = 1/4 + i/4 B = 1/4 - i/4
Therefore, we can express f(x) as:
f(x) = (1/4 + i/4)/(x - (1+2i)) + (1/4 - i/4)/(x - (1-2i))
(b) To determine the coefficient ar, we can use the formula:
ar = 1/(2πi) ∮ γ f(x)/xr+1 dx
where γ is a closed contour in the complex plane that encloses the origin in a counterclockwise direction, and the integral is taken along γ.
Using the residue theorem, we can evaluate this integral as the sum of the residues of f(x)/xr+1 at the poles inside γ. In this case, the poles are at x = 1+2i and x = 1-2i. We can compute the residues at these poles as:
Res(f(x)/xr+1, x = 1+2i) = lim(x→1+2i) ((x - (1+2i))f(x))/xr+1 = (1/4 + i/4)/(r+1)(1-2i)
Res(f(x)/xr+1, x = 1-2i) = lim(x→1-2i) ((x - (1-2i))f(x))/xr+1 = (1/4 - i/4)/(r+1)(1+2i)
Therefore, the coefficient ar is given by:
ar = 1/(2πi) ∮ γ f(x)/xr+1 dx = Res(f(x)/xr+1, x = 1+2i) + Res(f(x)/xr+1, x = 1-2i) = (1/4 + i/4)/(r+1)(1-2i)r + (1/4 - i/4)/(r+1)(1+2i)
Simplifying this expression, we get:
ar = (1/2r+2) ((-2/5)^(r+2) + 3(2/3)^(r+2))
3.
(a) We can express each odd integer as 2j+1 for some non-negative integer j. Then the equation becomes b1 + b2 + · · · + bk = 2j1 + 2j2 + · · · + 2jk, where each bi is a non-negative integer and each j1, j2, . . . , jk is a non-negative integer. Now, we can...