Question

A) Find the generating function of the recurrence
an = 4an−1 −4an−2 +1
with initial conditions a0 = 1, a1 = 1.
B) Express 3x4 +2x3 −2x2 +x in terms of [x]4, [x]3, [x]2 and [x]

Answer 1

Answer on Question #81204 – Math – Discrete Mathematics Question

A) Find the generating function of the recurrence

$$a_n = 4a_{n-1} - 4a_{n-2} + 1$$

with initial conditions $a_0 = 1, a_1 = 1$

Solution

Compute

$$a_2 = 4a_1 - 4a_0 + 1 = 4 - 4 + 1 = 1,$$ $$a_3 = 4a_2 - 4a_1 + 1 = 4 - 4 + 1 = 1$$

and so on.

The generating function is given by the formula

$$A = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + \cdots = 1 + x + x^2 + x^3 + x^4 + \cdots$$

Then

$$-xA = -x - x^2 - x^3 - x^4 - x^5 - \cdots$$

Adding the right-hand sides of $A$ and $-xA$ one gets

$$(1 - x)A = 1$$

Answer:

$$A = \frac{1}{1 - x}$$

Question

B) Express $3x^4 + 2x^3 - 2x^2 + x$ in terms of $x^4, x^3, x^2$ and $x$

Answer: 3, 2, -2, 1.

Answer provided by https://www.AssignmentExpert.com