Each day your supply of magic chocolate covered espresso beans doubles (each one splits in half), but then you eat 5 of them. You have 10 at the start of day 0.
Write out the first few terms of the sequence. Then give a recursive definition for the sequence and explain how you know it is correct.
In this chapter we explored sequences and mathematical induction. At first these might not seem entirely related, but there is a link: recursive reasoning. When we have many cases (maybe infinitely many), it is often easier to describe a particular case by saying how it relates to other cases, instead of describing it absolutely. For sequences, we can describe the \(n\)th term in the sequence by saying how it is related to the previous term. When showing a statement involving the variable \(n\) is true for all values of \(n\text{,}\) we can describe why the case for \(n = k\) is true on the basis of why the case for \(n = k-1\) is true.
While thinking of problems recursively is often easier than thinking of them absolutely (at least after you get used to thinking in this way), our ultimate goal is to move beyond this recursive description. For sequences, we want to find closed formulas for the \(n\)th term of the sequence. For proofs, we want to know the statement is actually true for a particular \(n\) (not only under the assumption that the statement is true for the previous value of \(n\)). In this chapter we saw some methods for moving from recursive descriptions to absolute descriptions.
If the terms of a sequence increase by a constant difference or constant ratio (these are both recursive descriptions), then the sequences are arithmetic or geometric, respectively, and we have closed formulas for each of these based on the initial terms and common difference or ratio.
If the terms of a sequence increase at a polynomial rate (that is, if the differences between terms form a sequence with a polynomial closed formula), then the sequence is itself given by a polynomial closed formula (of degree one more than the sequence of differences).
If the terms of a sequence increase at an exponential rate, then we expect the closed formula for the sequence to be exponential. These sequences often have relatively nice recursive formulas, and the characteristic root technique allows us to find the closed formula for these sequences.
If we want to prove that a statement is true for all values of \(n\) (greater than some first small value), and we can describe why the statement being true for \(n = k\) implies the statement is true for \(n = k+1\text{,}\) then the principle of mathematical induction gives us that the statement is true for all values of \(n\) (greater than the base case).
Throughout the chapter we tried to understand why these facts listed above are true. In part, that is what proofs, by induction or not, attempt to accomplish: they explain why mathematical truths are in fact truths. As we develop our ability to reason about mathematics, it is a good idea to make sure that the methods of our reasoning are sound. The branch of mathematics that deals with deciding whether reasoning is good or not is mathematical logic, the subject of the next chapter.
Find a closed formula for \(a_n\text{,}\) the \(n\)th term of the sequence, by writing each term as a sum of a sequence. Hint: first find \(a_0\text{,}\) but ignore it when collapsing the sum.
Find a closed formula again, this time using either polynomial fitting or the characteristic root technique (whichever is appropriate). Show your work.
The sequence \((a_n)_{n \ge 1}\) starts \(-1, 0, 2, 5, 9, 14\ldots\) and has closed formula \(a_n = \dfrac{(n+1)(n-2)}{2}\text{.}\) Use this fact to find a closed formula for the sequence \((b_n)_{n \ge 1}\) which starts \(4, 10, 18, 28, 40, \ldots\text{.}\)
The in song The Twelve Days of Christmas, my true love gave to me first 1 gift, then 2 gifts and 1 gift, then 3 gifts, 2 gifts and 1 gift, and so on. How many gifts did my true love give me all together during the twelve days?
Your magic chocolate bunnies reproduce like rabbits: every large bunny produces 2 new mini bunnies each day, and each day every mini bunny born the previous day grows into a large bunny. Assume you start with 2 mini bunnies and no bunny ever dies (or gets eaten).
