Chapter 10: Problem 15
Solve the recurrence relation \(a_{n+2}=a_{n+1} a_{n}, n \geq 0, a_{0}=1\), \(a_{1}=2\)
Short Answer
Step by step solution
Key Concepts
These are the key concepts you need to understand to accurately answer the question.
/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none}
Learning Materials
Features
Discover
Chapter 10: Problem 15
Solve the recurrence relation \(a_{n+2}=a_{n+1} a_{n}, n \geq 0, a_{0}=1\), \(a_{1}=2\)
These are the key concepts you need to understand to accurately answer the question.
All the tools & learning materials you need for study success - in one app.
Get started for free
Let \(A=\left[\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right]\) a) Compute \(A^{2}, A^{3}\), and \(A^{4}\). b) Conjecture a general formula for \(A^{n}, n \in \mathbf{Z}^{+}\), and establish your conjecture by the Principle of Mathematical Induction.
For \(\alpha=(1+\sqrt{5}) / 2\) and \(\beta=(1-\sqrt{5}) / 2\), show that \(\sum_{k=0}^{\infty} \beta^{k}=-\beta=\alpha-1\) and that \(\sum_{k=0}^{\infty}|\beta|^{k}=\alpha^{2}\)
In Corollary \(10.2\) we were concerned with finding the appropriate "big-Oh" form for a function \(f: \mathbf{Z}^{+} \rightarrow \mathbf{R}^{+} \cup\\{0\\}\) where \(\begin{aligned} f(1) \leq & c, \quad \text { for } c \in \mathbf{Z}^{+} \\\ f(n) \leq & a f(n / b)+c, \\ & \text { for } a, b \in \mathbf{Z}^{+} \text {with } b \geq 2 \text {, and } n=b^{k}, k \in \mathbf{Z}^{+} \end{aligned}\) Here the constant \(c\) in the second inequality is interpreted as he amount of time needed to break down the given problem of size \(n\) into \(a\) smaller (similar) problems of size \(n / b\) and to combine the \(a\) solutions of these smaller problems in order to set a solution for the original problem of size \(n\). Now we shall examine a situation wherein this amount of time is no longer a) Let \(a, b, c \in \mathbf{Z}^{+}\), with \(b \geq 2\). Let \(f: \mathbf{Z}^{+} \rightarrow \mathbf{R}^{+} \cup\\{0\\}\) be a monotone increasing function, where $$ \begin{aligned} &f(1) \leq c \\ &f(n) \leq a f(n / b)+c n, \quad \text { for } n=b^{k}, \quad k \in \mathbf{Z}^{+} \end{aligned} $$ Use an argument similar to the one given (for equalities) in Theorem \(10.1\) to show that for all \(n=1, b, b^{2}, b^{3}, \ldots\), $$ f(n) \leq c n \sum_{t=0}^{k}(a / b)^{\prime} $$ b) Use the result of part (a) to show that \(f \in O(n \log n)\), where \(a=b\). (The base for the log function here is any real number greater than 1.) c) When \(a \neq b\), show that part (a) implies that $$ f(n) \leq\left(\frac{c}{a-b}\right)\left(a^{k+1}-b^{k+1}\right) $$ d) From part (c), prove that (i) \(f \in O(n)\), when \(ab\). [Note: The "big-Oh" form for \(f\) here and in part (b) is for \(f\) on \(\mathbf{Z}^{+}\), not just \(\left\\{b^{k} \mid k \in \mathbf{N}\right\\} .\) ]
The number of bacteria in a culture is 1000 (approximately), and this number increases \(250 \%\) every two hours. Use a recurrence relation to determine the number of bacteria present after one day.
If Laura invests \(\$ 100\) at \(6 \%\) interest compounded quarterly, how many months must she wait for her money to double? (She cannot withdraw the money before the quarter is up.)
What do you think about this solution?
We value your feedback to improve our textbook solutions.