Chapter 5

Express each quotient as a sum of partial fractions. $$\frac{x+7}{(x-1)(x+3)}$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &s_{0}=1\\\ &s_{n}=2 s_{n-1}, n \geq 1 \end{aligned}$$

In Exercises \(1-6, a_{n}\) denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$ \begin{array}{l}{a_{1}=1} \\ {a_{n}=a_{n-1}+3, n \geq 2}\end{array} $$

Find a big-oh estimate for each. The number \(h(n)\) of handshakes made by \(n\) guests at a party, using Example 5.3

A_{n} denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$\begin{aligned} &a_{1}=1\\\ &a_{n}=a_{n-1}+3, n \geq 2 \end{aligned}$$

The number \(b_{n}\) of moves needed to transfer \(n\) disks in the Tower of Brahma puzzle in Example \(5.4 .\)

Express each quotient as a sum of partial fractions. $$\frac{4 x^{2}-3 x-25}{(x+1)(x-2)(x+3)}$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &a_{1}=1\\\ &a_{n}=a_{n-1}+n, n \geq 2 \end{aligned}$$

In Exercises \(1-6, a_{n}\) denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$ \begin{array}{l}{a_{0}=1} \\ {a_{n}=a_{n-1}+n, n \geq 1}\end{array} $$

Find a big-oh estimate for each. The number \(b_{n}\) of moves needed to transfer \(n\) disks in the Tower of Brahma puzzle in Example 5.4

A_{n} denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$\begin{aligned} &a_{0}=1\\\ &a_{n}=a_{n-1}+n, n \geq 1 \end{aligned}$$

Express each quotient as a sum of partial fractions. $$\frac{5}{1-x-6 x^{2}}$$

Determine if each recurrence relation is a LHRRWCC. $$a_{n}=1.08 a_{n-1}$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{array}{l} a_{0}=1 \\ a_{n}=a_{n-1}+n, n \geq 1 \end{array}$$

In Exercises \(1-6, a_{n}\) denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$ \begin{array}{l}{a_{1}=1} \\ {a_{n}=\frac{n}{n-1} a_{n-1}, n \geq 2}\end{array} $$

A_{n} denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$\begin{aligned} &a_{1}=1\\\ &a_{n}=\frac{n}{n-1} a_{n-1}, n \geq 2 \end{aligned}$$

Estimate the solution \(f_{n}\) of each recurrence relation (see Exercises 5.2 ). $$\begin{aligned} &f_{1}=1\\\ &f_{n}=f_{n-1}+(2 n-1), n \geq 2 \end{aligned}$$

Express each quotient as a sum of partial fractions. $$\frac{2+4 x}{1+8 x+15 x^{2}}$$

Determine if each recurrence relation is a LHRRWCC. $$b_{n}=2 b_{n-1}+1$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &a_{1}=1\\\ &a_{n}=a_{n-1}+(2 n-1), n \geq 2 \end{aligned}$$

In Exercises \(1-6, a_{n}\) denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$ \begin{array}{l}{a_{1}=1, a_{2}=2} \\ {a_{n}=a_{n-1}+a_{n-2}, n \geq 3}\end{array} $$

A_{n} denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$\begin{aligned} &a_{1}=1, a_{2}=2\\\ &a_{n}=a_{n-1}+a_{n-2}, n \geq 3 \end{aligned}$$

Using Algorithm \(5.4,\) find the number of computations needed to compute the \(n\) th Fibonacci number \(F_{n}\) for each value of \(n .\) (Hint: Draw a tree diagram.? $$4$$

Solving Recurrence Relations Revisited $$a_{n}=a_{n-1}+n$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &a_{0}=0\\\ &a_{n}=a_{n-1}+4 n, n \geq 1 \end{aligned}$$

Estimate the solution \(f_{n}\) of each recurrence relation (see Exercises 5.2 ). $$\begin{aligned} &f_{0}=0\\\ &f_{n}=f_{n-1}+4 n, n \geq 1 \end{aligned}$$

Express each quotient as a sum of partial fractions. $$\frac{x(x+2)}{(2+3 x)\left(x^{2}+1\right)}$$

Estimate the solution \(f_{n}\) of each recurrence relation (see Exercises 5.2 ). $$\begin{aligned} &f_{1}=2\\\ &f_{n}=f_{n-1}+n, n \geq 2 \end{aligned}$$

Express each quotient as a sum of partial fractions. $$\frac{-2 x^{2}-2 x+2}{(x-1)\left(x^{2}+2 x\right)}$$

Using Algorithm \(5.4,\) find the number of computations needed to compute the \(n\) th Fibonacci number \(F_{n}\) for each value of \(n .\) (Hint: Draw a tree diagram.? $$5$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &s_{1}=1\\\ &s_{n}=s_{n-1}+n^{3}, n \geq 2 \end{aligned}$$

In Exercises \(1-6, a_{n}\) denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$ \begin{array}{l}{a_{1}=1, a_{2}=2, a_{3}=3} \\\ {a_{n}=a_{n-1}+a_{n-2}+a_{n-3}, n \geq 4}\end{array} $$

Solving Recurrence Relations Revisited $$a_{n}=2 a_{n-1}+\left(2^{n}-1\right)$$

A_{n} denotes the \(n\) th term of a number sequence satisfying the given initial condition(s) and the recurrence relation. Compute the first four terms of the sequence. $$\begin{aligned} &a_{1}=1, a_{2}=2, a_{3}=3\\\ &a_{n}=a_{n-1}+a_{n-2}+a_{n-3}, n \geq 4 \end{aligned}$$

Express each quotient as a sum of partial fractions. $$\frac{x^{3}+x^{2}+x+3}{x^{4}+5 x^{2}+6}$$

Using Algorithm \(5.4,\) find the number of computations needed to compute the \(n\) th Fibonacci number \(F_{n}\) for each value of \(n .\) (Hint: Draw a tree diagram.? $$6$$

The \(n\) th Lucas number \(L_{n},\) named after the French mathematician François-Edouard-Anatole Lucas, is defined recursively as follows: $$\begin{array}{l} L_{1}=1, \quad L_{2}=3 \\ L_{n}=L_{n-1}+L_{n-2}, n \geq 3 \end{array}$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{aligned} &s_{1}=1\\\ &s_{n}=s_{n-1}+n^{2}, n \geq 2 \end{aligned}$$

Estimate the solution \(f_{n}\) of each recurrence relation (see Exercises 5.2 ). $$\begin{aligned} &f_{1}=1\\\ &f_{n}=2 f_{n-1}+\left(2^{n}-1\right), n \geq 2 \end{aligned}$$

Find the number of comparisons needed to search for \(k e y=13\) in each ordered list using the recursive binary search algorithm in Example 5.33 $$1,2,3,5,8,13$$

Express each quotient as a sum of partial fractions. $$\frac{-x^{3}+2 x^{2}+x}{x^{4}+x^{3}+x+1}$$

Solving Recurrence Relations Revisited $$a_{n}=a_{n-1}+2 a_{n-3}+n^{2}$$

(The Lucas sequence and the Fibonacci sequence satisfy the same recurrence relation, but have different initial conditions.) Compute the first six Lucas numbers. The ged of two integers \(x(>0)\) and \(y(\geq 0)\) can be defined recursively as follows: $$\operatorname{gcd}\\{x, y\\}=\left\\{\begin{array}{ll} \operatorname{gcd}\\{y, x\\} & \text { if } y>x \\ x & \text { if } y \leq x \text { and } y=0 \\ \operatorname{gcd}\\{y, x \bmod y\\} & \text { if } y \leq x \text { and } y>0 \end{array}\right.$$ Using this definition, compute the gcd of each pair of integers. $$28,18$$

Using the iterative method, predict a solution to each recurrence relation satisfying the given initial condition. $$\begin{array}{l} a_{1}=1 \\ a_{n}=2 a_{n-1}+\left(2^{n}-1\right), n \geq 2 \end{array}$$

Find the number of comparisons needed to search for \(k e y=13\) in each ordered list using the recursive binary search algorithm in Example 5.33 $$5,8,13,21,34$$

Express each quotient as a sum of partial fractions. $$\frac{3 x^{3}-x^{2}+4 x}{x^{4}-x^{3}+2 x^{2}-x+1}$$

Solve each LHRRWCC. $$a_{n}=a_{n-1}+2 a_{n-2}, a_{0}=3, a_{1}=0$$

Find the number of comparisons needed to search for \(k e y=13\) in each ordered list using the recursive binary search algorithm in Example 5.33 $$3,7,8,13,21$$

Express each quotient as a sum of partial fractions. $$\frac{x^{3}+x^{2}+5 x-2}{x^{4}-x^{2}+x-1}$$

Solve each LHRRWCC. $$a_{n}=5 a_{n-1}-6 a_{n-2}, a_{0}=4, a_{1}=7$$