Chapter 5

Prove that \(h_{n}=p_{n}+t_{n}-n,\) using the explicit formulas for \(p_{n}\) and \(t_{n}.\)

Prove that \(h_{n}=p_{n}+t_{n}-n,\) using the recurrence relations for \(p_{n}\) and \(t_{n} .\)

The \(n\) th term \(b_{n}\) of a number sequence is defined by \(b_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\) where \(\alpha=(1+\sqrt{5}) / 2\) and \(\beta=(1-\sqrt{5}) / 2\) are solutions of the equation \(x^{2}=x+1\) Verify each. $$b_{1}=1$$

The \(n\) th term \(b_{n}\) of a number sequence is defined by \(b_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\) where \(\alpha=(1+\sqrt{5}) / 2\) and \(\beta=(1-\sqrt{5}) / 2\) are solutions of the equation \(x^{2}=x+1\) Verify each. $$b_{2}=1$$

Let \(f\) be a function defined by \(f(n)=a f(n / b)+c n,\) where \(a, b \in \mathbb{N}, b \geq 2\) \(c \in R^{+},\) and \(f(1)=d .\) Assume \(n\) is a power of \(b\) Let \(a=b\) and \(d=0 .\) Show that \(f(n)=\mathrm{O}(n \lg n)\)

Consider the recurrence relation \(c_{n}=c_{[n / 2]}+c_{[L n+1 / 2]}+2,\) where \(c_{1}=0\) Compute \(c_{3}\) and \(c_{4}\)

The \(n\) th term \(b_{n}\) of a number sequence is defined by \(b_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\) where \(\alpha=(1+\sqrt{5}) / 2\) and \(\beta=(1-\sqrt{5}) / 2\) are solutions of the equation \(x^{2}=x+1\) Verify each. $$b_{n}=b_{n-1}+b_{n-2}, n \geq 3$$

Consider the recurrence relation \(c_{n}=c_{\lfloor n / 2\rfloor}+c_{\lfloor(n+1) / 2 j}+2,\) where \(c_{1}=0\). Compute \(c_{3}\) and \(c_{4}\)

Consider the recurrence relation \(c_{n}=c_{[n / 2]}+c_{[L n+1 / 2]}+2,\) where \(c_{1}=0\) Solve the recurrence relation when \(n\) is a power of \(2 .\)

(It follows from Exercises \(48-50\) that \(b_{n}=F_{n}\) . It is called the Binet form of the \(n\) th Fibonaci number, after the French mathematician Jacques. Phillipe-Marie Binet.) With \(\alpha\) and \(\beta\) as above, let \(u_{n}=\alpha^{n}+\beta^{n}, n \geq 1\) . Verify each. $$ u_{1}=1 $$

Consider the recurrence relation \(c_{n}=c_{\lfloor n / 2\rfloor}+c_{\lfloor(n+1) / 2 j}+2,\) where \(c_{1}=0\). Solve the recurrence relation when \(n\) is a power of 2

That \(b_{n}=F_{n} .\) It is called the Binet form of the \(n\) th Fibonacci number, after the French mathematician JacquesPhillipe-Marie Binet.) With \(\alpha\) and \(\beta\) as above, let \(u_{n}=\alpha^{n}+\beta^{n}, n \geq 1 .\) Verify each. $$u_{1}=1$$

Consider the recurrence relation \(c_{n}=c_{[n / 2]}+c_{[L n+1 / 2]}+2,\) where \(c_{1}=0\) Find the order of magnitude of \(c_{n}\) when \(n\) is a power of \(2 .\)

(It follows from Exercises \(48-50\) that \(b_{n}=F_{n}\) . It is called the Binet form of the \(n\) th Fibonaci number, after the French mathematician Jacques. Phillipe-Marie Binet.) With \(\alpha\) and \(\beta\) as above, let \(u_{n}=\alpha^{n}+\beta^{n}, n \geq 1\) . Verify each. $$ u_{2}=3 $$

Consider the recurrence relation \(c_{n}=c_{\lfloor n / 2\rfloor}+c_{\lfloor(n+1) / 2 j}+2,\) where \(c_{1}=0\). Find the order of magnitude of \(c_{n}\) when \(n\) is a power of 2

That \(b_{n}=F_{n} .\) It is called the Binet form of the \(n\) th Fibonacci number, after the French mathematician JacquesPhillipe-Marie Binet.) With \(\alpha\) and \(\beta\) as above, let \(u_{n}=\alpha^{n}+\beta^{n}, n \geq 1 .\) Verify each. $$u_{1}=1$$

Let \(t\) be a function defined by $$ t(n)=\left\\{\begin{array}{ll} a & \text { if } n=1 \\ t(\lfloor n / 2\rfloor)+t(\lceil n / 2\rceil)+b n & \text { otherwise } \end{array}\right. $$ where \(a, b \in \mathbb{R}^{+} .\) (Such a function occurs in the analysis of merge sort.) Prove that \(t(n)\) is a non decreasing function; that is, \(t(n) \leq t(n+1)\) where \(n \geq 1\)

Let \(a_{1}, a_{2}, \ldots, a_{n} \in \mathbb{N},\) where \(n \geq 2\) . Prove that \(\operatorname{gcd}\left\\{a_{1}, a_{2}, \dots, a_{n}\right\\}=\operatorname{gcd}\left\\{\operatorname{gcd}\left\\{a_{1}, a_{2}, \dots, a_{n-1} |, a_{n}\right\\}\right.\)

[These exercises indicate that \(u_{n}=L_{n},\) the \(n\) th Lucas number. Accordingly, \(\left.u_{n}=\alpha^{n}+\beta^{n} \text { is the Binet form of } L_{n} .\right]\) Let \(a_{1}, a_{2}, \ldots, a_{n} \in \mathbb{N},\) where \(n \geq 2 .\) Prove that \(\operatorname{gcd}\left\\{a_{1}, a_{2}, \ldots, a_{n}\right\\}=\operatorname{gcd}\left\\{\operatorname{gcd}\left\\{a_{1}, a_{2}, \ldots, a_{n-1}\right\\}, a_{n}\right\\}\)

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that contain no consecutive integers, where \(n \geq 0 .\) When \(n=0, S=\emptyset\). Compute each. $$a_{0}$$

Let \(f(n)=2 f(n / 2)+c n^{2},\) where \(f(1)=d\) and \(n\) is a power of 2 Solve the recurrence relation.

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that contain no consecutive integers, where \(n \geq 0 .\) When \(n=0, S=\emptyset\). Compute each. $$a_{1}$$

Let \(f(n)=2 f(n / 2)+c n^{2},\) where \(f(1)=d\) and \(n\) is a power of 2 Show that \(f(n)=\mathbf{O}\left(n^{2}\right)\)

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that contain no consecutive integers, where \(n \geq 0 .\) When \(n=0, S=\emptyset\). Compute each. $$a_{2}$$

Let \(a_{n}\) denote the number of times the assignment statement \(x \leftarrow x+1\) is executed by each nested for loop. Define \(a_{n}\) recursively. $$ \begin{array}{c}{\text { for } 1=1 \text { to } n \text { do }} \\ {\text { for } j=1 \text { to } i \text { do }} \\ {x \leftarrow x+1}\end{array} $$

The number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right)\) called the harmonic number, occurs frequently in the analysis of algorithms. Compute \(h_{4}\) and \(h_{5}\)

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that contain no consecutive integers, where \(n \geq 0 .\) When \(n=0, S=\emptyset\). Compute each. $$a_{3}$$

Let \(a_{n}\) denote the number of times the assignment statement \(x \leftarrow x+1\) is executed by each nested for loop. Define \(a_{n}\) recursively. for \(i=1\) to \(n\) do for \(j=1\) to \(i\) do for \(k=1\) to 1 do $$x \leftarrow x+1$$

The number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right)\) called the harmonic number, occurs frequently in the analysis of algorithms. Define \(h_{n}\) recursively.

Let \(a_{n}\) denote the number of rectangles that can be formed on a \(1 \times n\) rectangular board. Find the recurrence relation satisfied by \(a_{n}\) (Hint: Look for a pattern. Every square is also a rectangle.)

The number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right),\) called the harmonic number, occurs frequently in the analysis of algorithms. Prove that \(\sum_{i=1}^{n} h_{i}=(n+1) h_{n}-n, n \geq 1\)

Let \(a_{n}\) denote the number of subsets of the set \(S=\\{1,2, \ldots, n\\}\) that contain no consecutive integers, where \(n \geq 0 .\) When \(n=0, S=\emptyset .\) Compute each. Solve the recurrence relation satisfied by \(a_{n}.\)

A subset of the set \(S=\\{1,2, \ldots, n | \text { is alternating if its elements, when }\) arranged in increasing order, follow the pattern odd, even, odd, even, etc. For example, \(\\{3\\},\\{1,2,5\\},\) and \(\\{3,4\\}\) are alternating subsets of \(\\{1,2,3,4,5 |\) whereas \(\\{1,3,4\\}\) and \(\\{2,3,4,5\\}\) are not; \(\emptyset\) is considered alternating. Let \(a_{n}\) denote the number of alternating subsets of \(S .\) Define \(a_{n}\) recursively.

Prove that \(\sum_{i=1}^{n} h_{i}=(n+1) h_{n}-n, n \geq 1\)

A subset of the set \(S=\\{1,2, \ldots, n\\}\) is alternating if its elements, when arranged in increasing order, follow the pattern odd, even, odd, even, etc. For example, \(\\{3\\},\\{1,2,5\\},\) and \\{3,4\\} are alternating subsets of \\{1,2,3,4,5\\} whereas \\{1,3,4\\} and \\{2,3,4,5\\} are not; \(\emptyset\) is considered alternating." Let\(a_{n}\) denote the number of alternating subsets of \(S\) Define \(a_{n}\) recursively.

Suppose we introduce a mixed pair of -month-old rabbits into a large enclosure on the first day of a certain month. By the end of each month, the rabbits become mature and each pair produces \(k-1\) mixed pairs of offspring at the beginning of the following month. Wote: \(k \geq 2 .\) ) For instance, at the beginning of the second month, there is one pair of 2 -month-old rabbits and \(k-1\) pairs of 0 -month-olds; at the beginning of the third month, there is one pair of 3-month-olds, \(k-1\) pairs of 1 -month-olds, and \(k(k-1)\) pairs of 0 -month-olds. Assume the rabbits are immortal. Let \(a_{n}\) denote the average age of the rabbit pairs at the beginning of the \(n\) month. (P. Filiponi, 1990 ) Define \(a_{n}\) recursively.

A subset of the set \(S=\\{1,2, \ldots, n | \text { is alternating if its elements, when }\) arranged in increasing order, follow the pattern odd, even, odd, even, etc. For example, \(\\{3\\},\\{1,2,5\\},\) and \(\\{3,4\\}\) are alternating subsets of \(\\{1,2,3,4,5 |\) whereas \(\\{1,3,4\\}\) and \(\\{2,3,4,5\\}\) are not; \(\emptyset\) is considered alternating. Let \(a_{n}\) denote the number of alternating subsets of \(S .\) Prove that \(a_{n}=F_{n+2},\) where \(F_{n}\) denotes the \(n\) th Fibonacci number.

Stirling numbers of the second kind, denoted by \(S(n, r)\) and used in combinatorics, are defined recursively as follows, where \(n, r \in \mathbb{N}\) : $$S(n, r)=\left\\{\begin{array}{ll}1 & \text { if } r=1 \text { or } r=n \\\S(n-1, r-1)+r S(n-1, r) & \text { if } 1n\end{array}\right.$$ They are named after the English mathematician James Stirling (1692- 1770). Compute each Stirling number. $$S(2,2)$$

Prove that \(h_{n} \leq \frac{n+1}{2}\)

Suppose we introduce a mixed pair of 1-month-old rabbits into a large enclosure on the first day of a certain month. By the end of each month, the rabbits become mature and each pair produces \(k-1\) mixed pairs of offspring at the beginning of the following month. (Note: \(k \geq 2 .\) ) For instance, at the beginning of the second month, there is one pair of 2-month-old rabbits and \(k-1\) pairs of 0 -month-olds; at the beginning of the third month, there is one pair of 3-month-olds, \(k-1\) pairs of 1-month-olds, and \(k(k-1)\) pairs of 0 -month-olds. Assume the rabbits are immortal. Let \(a_{n}\) denote the average age of the rabbit pairs at the beginning of the \(n\) th month. (P. Filipponi, 1990). Predict an explicit formula for \(a_{n}\).

The number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right),\) called the harmonic number, occurs frequently in the analysis of algorithms. (For those familiar with calculus) Let \(h_{n}\) denote the \(n\) th harmonic number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right)\) . Show that \(h_{n}=O(\lg n)\) (Hint: Use integration.)

(For those familiar with calculus) Let \(h_{n}\) denote the \(n\) th harmonic number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right) .\) Show that \(h_{n}=\mathrm{O}(\lg n)\)

The number \(h_{n}=\sum_{i=1}^{n}\left(\frac{1}{i}\right),\) called the harmonic number, occurs frequently in the analysis of algorithms. Solve the recurrence relation \(g_{n}-g_{n-1}=1 /(n-1) !,\) where \(g_{1}=0\)

Suppose we introduce a mixed pair of -month-old rabbits into a large enclosure on the first day of a certain month. By the end of each month, the rabbits become mature and each pair produces \(k-1\) mixed pairs of offspring at the beginning of the following month. Wote: \(k \geq 2 .\) ) For instance, at the beginning of the second month, there is one pair of 2 -month-old rabbits and \(k-1\) pairs of 0 -month-olds; at the beginning of the third month, there is one pair of 3-month-olds, \(k-1\) pairs of 1 -month-olds, and \(k(k-1)\) pairs of 0 -month-olds. Assume the rabbits are immortal. Let \(a_{n}\) denote the average age of the rabbit pairs at the beginning of the \(n\) month. (P. Filiponi, 1990 ) (For those familiar with the concept of limits) Find \(\lim _{n \rightarrow \infty} a_{n}\)

A function of theoretical importance in the study of algorithms is the Ackermann's function, named after the German mathematician and logician Wilhelm Ackermann (1896-1962). It is defined recursively as follows, where \(m, n \in \mathbf{W}:\) $$A(m, n)=\left\\{\begin{array}{ll}n+1 & \text { if } m=0 \\\A(m-1,1) & \text { if } n=0 \\\A(m-1, A(m, n-1)) & \text { otherwise }\end{array}\right.$$ Compute each. $$A(0,7)$$

Solve the recurrence relation \(g_{n}-g_{n-1}=1 /(n-1) !,\) where \(g_{1}=0\)

A function of theoretical importance in the study of algorithms is the Ackermann's function, named after the German mathematician and logician Wilhelm Ackermann (1896-1962). It is defined recursively as follows, where \(m, n \in \mathbf{W}:\) $$A(m, n)=\left\\{\begin{array}{ll}n+1 & \text { if } m=0 \\\A(m-1,1) & \text { if } n=0 \\\A(m-1, A(m, n-1)) & \text { otherwise }\end{array}\right.$$ Compute each. $$A(1,1)$$

Let \(a, b \in \mathbb{N}\) and \(c, d \in \mathbb{R}^{+}\) with \(b \geq 2 .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c\) and \(f(1)=d .\) Prove each. $$\text { If } a=1, \text { then } f(n)=\mathrm{O}(\lg n)$$

Let \(a, b \in \mathbb{N}\) and \(c, d \in \mathbb{R}^{+}\) with \(b \geq 2 .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c\) and \(f(1)=d .\) Prove each. $$\text { If } a \neq 1, \text { then } f(n)=\mathrm{O}\left(n^{\log _{b} a}\right)$$

A function of theoretical importance in the study of algorithms is the Ackermann's function, named after the German mathematician and logician Wilhelm Ackermann (1896-1962). It is defined recursively as follows, where \(m, n \in \mathbf{W}:\) $$A(m, n)=\left\\{\begin{array}{ll}n+1 & \text { if } m=0 \\\A(m-1,1) & \text { if } n=0 \\\A(m-1, A(m, n-1)) & \text { otherwise }\end{array}\right.$$ Compute each. $$A(4,0)$$