Chapter 8

What sequences have the following generating functions? (a) 1 (b) \(\frac{10}{2-z}\) (c) \(1+z\) (d) \(\frac{3}{1+2 x}+\frac{3}{1-3 x}\)

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-10 S(k-1)+9 S(k-2)=0, S(0)=3, S(1)=11 $$

Solve the following recurrence relations. Indicate whether your solution is an improvement over iteration. (a) \(n S(n)-S(n-1)=0, S(0)=1\). (b) \(T(k)+3 k T(k-1)=0, T(0)=1\). (c) \(U(k)-\frac{k-1}{k} U(k-1)=0, k \geq 2, U(1)=1\).

By the recursive definition of binomial coefficients, \(\left(\begin{array}{c}7 \\\ 2\end{array}\right)=\left(\begin{array}{c}6 \\\ 2\end{array}\right)+\left(\begin{array}{c}6 \\ 1\end{array}\right) .\) Continue expanding \(\left(\begin{array}{l}7 \\ 2\end{array}\right)\) to express it in terms of quantities defined by the basis. Check your result by applying the factorial definition of \(\left(\begin{array}{c}n \\\ k\end{array}\right)\).

What sequences have the following generating functions? (a) \(\frac{1}{1+z}\) (b) \(\frac{1}{4-3 z}\) (c) \(\frac{2}{1-2}+\frac{1}{1+z}\) (d) \(\frac{z+2}{z+3}\)

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-9 S(k-1)+18 S(k-2)=0, S(0)=0, S(1)=3 $$

Prove that if \(n \geq 0,\lfloor n / 2\rfloor+\lceil n / 2\rceil=n\).

Define the sequence \(L\) by \(L_{0}=5\) and for \(k \geq 1, L_{k}=2 L_{k-1}-7\). Determine \(L_{4}\) and prove by induction that \(L_{k}=7-2^{k+1}\).

Given \(k\) lines \((k \geq 0)\) on a plane such that no two lines are parallel and no three lines meet at the same point, let \(P(k)\) be the number of regions into which the lines divide the plane (including the infinite ones (see Figure 8.2.3). Describe how the recurrence relation \(P(k)=P(k-\text { 1) }+k \text { can be derived. Given that } P(0)=1 \text { , determine } P(5) \text { . }\)

Find closed form expressions for the generating functions of the following sequences: (a) \(V(n)=9^{n}\) (b) \(P,\) where \(P(k)-6 P(k-1)+5 P(k-2)=0\) for \(k \geq 2,\) with \(P(0)=2\) and \(P(1)=2\) (c) The Fibonacci sequence: \(F(k+2)=F(k+1)+F(k), k \geq 0,\) with \(F(0)=F(1)=1\)

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-0.25 S(k-1)=0, S(0)=6 $$

Solve as completely as possible: (a) \(T(n)=3+T(\lfloor n / 2\rfloor), T(0)=0\). (b) \(T(n)=1+\frac{1}{2} T(\lfloor n / 2\rfloor), T(0)=2\). (c) \(V(n)=1+V\lfloor n / 8\rfloor), V(0)=0\).

Let \(p(x)=x^{5}+3 x^{4}-15 x^{3}+x-10\). (a) Write \(p(x)\) in telescoping form. (b) Use a calculator to compute \(p(3)\) using the original form of \(p(x)\). (c) Use a calculator to compute \(p(3)\) using the telescoping form of \(p(x)\). (d) Compare your speed in parts b and c.

A sample of a radioactive substance is expected to decay by 0.15 percent each hour. If \(w_{t}, t \geq 0,\) is the weight of the sample \(t\) hours into an experiment, write a recurrence relation for \(w\).

Find closed form expressions for the generating functions of the following sequenoes: (a) \(W(n)=\left(\begin{array}{l}5 \\ n\end{array}\right) 2^{n}\) for \(0 \leq n \leq 5\) and \(W(n)=0\) for \(n>5 .\) (b) \(Q,\) where \(Q(k)+Q(k-1)-42 Q(k-2)=0\) for \(k \geq 2\), with \(Q(0)=2\) and \(Q(1)=2\). (c) \(G,\) where \(G(k+3)=G(k+2)+G(k+1)+G(k)\) for \(k \geq 0,\) with \(G(0)=G(1)=G(2)=1\)

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-20 S(k-1)+100 S(k-2)=0, S(0)=2, S(1)=50 $$

Prove by induction that if \(T(n)=1+T(\lfloor n / 2\rfloor), T(0)=0,\) and \(2^{r-1} \leq\) \(n<2^{r}, r \geq 1,\) then \(T(n)=r\)

Suppose that a list of nine items, \((r(l), r(2), \ldots, r(9)),\) is sorted by key in decending order so that \(r(3)\).key \(=12\) and \(r(4)\).key \(=10\). List the executions of the BinarySearch algorithms that would be needed to complete BinarySearch (1,9) when: (a) The search key is \(\mathrm{C}=12\) (b) The search key is \(\mathrm{C}=11\)

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-2 S(k-1)+S(k-2)=2, S(0)=25, S(1)=16 $$

Use the substitution \(S(n)=T(n+1) / T(n)\) to solve \(T(n) T(n-2)=\) \(T(n-1)^{2}\) for \(n \geq 2,\) with \(T(0)=1, T(1)=6,\) and \(T(n) \geq 0\).

What is wrong with the following definition of \(f: \mathbb{R} \rightarrow \mathbb{R} ? f(0)=1\) and \(f(x)=f(x / 2) / 2\) if \(x \neq 0\).

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-S(k-1)-6 S(k-2)=-30, S(0)=7, S(1)=10 $$

Use the substitution \(G(n)=T(n)^{2}\) to solve \(T(n)^{2}-T(n-1)^{2}=1\) for \(n \geq 1,\) with \(T(0)=10\).

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-5 S(k-1)=5^{k}, S(0)=3 $$

Solve as completely as possible: (a) \(Q(n)=1+Q(\lfloor\sqrt{n}\rfloor), n \geq 2, Q(1)=0\). (b) \(R(n)=n+R(\lfloor n / 2\rfloor), n \geq 1, R(0)=0 .\)

Prove by induction that if \(n \geq 0, \sum_{k=0}^{n}\left(\begin{array}{c}n \\\ k\end{array}\right)=2^{n}\).

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-5 S(k-1)+6 S(k-2)=2, S(0)=-1, S(1)=0 $$

Suppose Step 1 of the merge sort algorithm did take a significant amount of time. Assume it takes 0.1 time unit, independent of the value of \(n\). (a) Write out a new recurrence relation for \(T(n)\) that takes this factor into account. (b) Solve for \(T\left(2^{r}\right), r \geq 0\) (c) Assuming the solution for powers of 2 is a good estimate for all \(n\), compare your result to the solution in the text. As gets large, is there really much difference?

A game is played by rolling a die five times. For the \(k^{\text {th }}\) roll, one point is added to your score if you roll a number higher than \(k .\) Otherwise, your score is zero for that roll. For example, the sequence of rolls 2,3,4,1,2 gives you a total score of three; while a sequence of 1.2,3,4,5 gives you a score of zero. Of the \(6^{5}=7776\) possible sequences of rolls, how many give you a score of zero? of one? ... of five?

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-4 S(k-1)+4 S(k-2)=3 k+2^{k}, S(0)=1, S(1)=1 $$

Suppose that you roll a die ten times in a row and record the square of each number that you roll. How many ways could the sum of the squares of your rolls equal \(40 ?\) What is the most common outcome?

Solve the following sets of recurrence relations and initial conditions: $$ S(k)=r S(k-1)+a, S(0)=0, r, a \geq 0, r \neq 1 $$

Solve the following sets of recurrence relations and initial conditions: $$ \begin{array}{l} S(k)-4 S(k-1)-11 S(k-2)+30 S(k-3)=0, S(0)=0, S(1)= -35, S(2)=-85 \end{array} $$

(a) Find a closed form expression for the terms of the Fibonacci sequence (see Example 8.1.8). (b) The sequence \(C\) was defined by \(C_{r}=\) the number of strings of zeros and ones with length \(r\) having no consecutive zeros (Example \(8.2 .2(\mathrm{c})) .\) Its recurrence relation is the same as that of the Fibonacci sequence. Determine a closed form expression for \(C_{r}, r \geq 1\)

If \(S(n)=\sum_{j=1}^{n} g(j), n \geq 1,\) then \(S\) can be described with the recurrence relation \(S(n)=S(n-1)+g(n)\). For each of the following sequences that are defined using a summation, find a closed form expression: (a) \(S(n)=\sum_{j=1}^{n} j, n \geq 1\) (b) \(Q(n)=\sum_{j=1}^{n} j^{2}, n \geq 1\) (c) \(P(n)=\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j}, n \geq 0\) (d) \(T(n)=\sum_{j=1}^{n} j^{3}, n \geq 1\)

Let \(D(n)\) be the number of ways that the set \(\\{1,2, \ldots, n\\}, n \geq 1,\) can be partitioned into two nonempty subsets. (a) Find a recurrence relation for \(D\). (Hint: It will be a first-order linear relation.) (b) Solve the recurrence relation.

Suppose that \(C\) is a small positive number. Consider the recurrence relation \(B(k)-2 B(k-1)+\left(1-C^{2}\right) B(k-2)=C^{2},\) with initial conditions \(B(0)=1\) and \(B(1)=1 .\) If \(C\) is small enough, we might consider approximating the relation by replacing \(1-C^{2}\) with 1 and \(C^{2}\) with 0. Solve the original relation and its approximation. Let \(B_{a}\) a be the solution of the approximation. Compare closed form expressions for \(B(k)\) and \(B_{a}(k)\). Their forms are very different because the characteristic roots of the original relation were close together and the approximation resulted in one double characteristic root.If characteristic roots of a relation are relatively far apart, this problem will not occur. For example, compare the general solutions of \(S(k)+1.001 S(k-1)-2.004002 S(k-2)=0.0001\) and \(S_{a}(k)+S_{a}(k-1)-2 S_{a}(k-2)=0\)