Vaša košarica je prazna
Recursive sequences – examples
In the following examples we will see another way to define number sequences.
Example 1
We are climbing a staircase consisting of \latex{ n } (\latex{n \geq 1} is an integer) stairs in such a way that we can always go up by one or two steps. In how many different ways can we reach the top?
Solution
It is worth finding the solution for \latex{ 1;\, 2;\, 3 } or \latex{ 4 } steps.
Let ln denote the number of possibilities for \latex{ n } steps.
The following three cases are trivial:
The following three cases are trivial:
\latex{l_1=1, \;l_2=2,\;l_3=3.}
Observe that we can reach step \latex{ 4 } by stepping up by \latex{ 1 } from step \latex{ 3 }, or directly from step \latex{ 2 } by stepping up by \latex{ 2 }. This means that
\latex{l_4=l_3+l_2=3+2=5.}
We can proceed in a similar fashion:
\latex{l_5=l_4+l_3=5+3=8,}
\latex{l_6=l_5+l_4=8+5=13,}
\latex{l_6=l_5+l_4=8+5=13,}
in general,
\latex{l_{n+2}=l_{n+1}+l_n.}
Thus the first two terms of the sequence \latex{l_n} are \latex{ 1 } and \latex{ 2 }, and any further term is the sum of the previous two.
Example 2
In how many ways can we cover (one layer, without gaps) a rectangle of size \latex{n \times 2} with dominoes of size \latex{1 \times 2}?
\latex{n=1,\;\;t_1=1}
\latex{n=2,\;\;t_2=2}
Figure 6
Solution
Let \latex{t_n} denote the number of possible coverings. Again, it is worth finding the value of \latex{t_1}, \latex{t_2}, \latex{t_3}.
Clearly \latex{t_1 = 1}, \latex{t_2 = 2} (Figure 6), \latex{t_3 = 3} (Figure 7).
Clearly \latex{t_1 = 1}, \latex{t_2 = 2} (Figure 6), \latex{t_3 = 3} (Figure 7).
We can observe that if we extend a covering of a \latex{3\times2} rectangle with a “vertical” domino to the right, we get a covering of the \latex{4\times2}, and if we extend a covering of the \latex{4\times2} with two “horizontal” dominoes to the right, we get a covering of the \latex{4\times2}, too.
\latex{n=3,\;\;t_3=3}
Figure 7
Clearly we get every possible covering this way since any covering ends with either a “vertical” domino or two “horizontal” ones. Therefore
\latex{t_4=t_3+t_2=3+2=5.}
Similarly,\latex{t_5=t_4+t_3=5+3=8},
and in general,\latex{t_{n+2}=t_{n+1}+t_n}.
\latex{f_1=f_2=1},
\latex{f_{n+2}=f_{n+1}+f_n}.
\latex{f_{n+2}=f_{n+1}+f_n}.
The first few terms of the sequence are
\latex{f_1=1}, \latex{f_2=1}, \latex{f_3=2}, \latex{f_4=3}, \latex{f_5=5}, \latex{f_6=8},
\latex{f_7=13}, \latex{f_8=21}, \latex{f_9=34}, \latex{f_{10}=55}, \latex{f_{11}=89},
\latex{f_{12}=144}, \latex{f_{13}=233}, \latex{f_{14}=377}, \latex{f_{15}=610}, \latex{\dots}
\latex{f_7=13}, \latex{f_8=21}, \latex{f_9=34}, \latex{f_{10}=55}, \latex{f_{11}=89},
\latex{f_{12}=144}, \latex{f_{13}=233}, \latex{f_{14}=377}, \latex{f_{15}=610}, \latex{\dots}
We have already met the sequence, which is nowadays called Fibonacci sequence, at the start of the book for last year's studies.
The terms of the Fibonacci sequence are often called Fibonacci numbers.
Example 3
Sum the terms with odd indices from the Fibonacci sequence starting with the first up to the \latex{n^{th}}. What can we say about the sum?
Solution
By computing the first few cases we get
\latex{f_1=1},
\latex{f_1+f_3=1+2=3},
\latex{f_1+f_3+f_5=3+5=8},
\latex{f_1+f_3+f_5+f_7=8+13=21}.
\latex{f_1+f_3=1+2=3},
\latex{f_1+f_3+f_5=3+5=8},
\latex{f_1+f_3+f_5+f_7=8+13=21}.
It is easy to notice we always end up with a Fibonacci number. In particular, the next one after the last summand.
Indeed,
\latex{f_1+f_3+f_5+f_7+\dots+f_{2n-1}=\\=f_2+f_3+f_5+f_7+\dots+f_{2n-1}=f_4+f_5+f_7+\dots+f_{2n-1}=\\=f_6+f_7+\dots+f_{2n-1}=\dots=f_{2n-2}+f_{2n-1}.}
Example 4
Sum the squares of the terms of the Fibonacci sequence from the start up to the \latex{n^{th}}. What is the sum?
Solution I
Illustrate the terms of the sum by the area of a square with corresponding side length and place these squares next to each other in an appropriate way. (Figure 8)
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{2^2}
\latex{2^2}
\latex{2^2}
\latex{2^2}
\latex{2^2}
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{1^2}
\latex{3^2}
\latex{3^2}
\latex{3^2}
\latex{5^2}
\latex{5^2}
\latex{8^2}
\latex{1\times2}
\latex{2\times3}
\latex{3\times5}
\latex{5\times8}
\latex{8\times13}
Figure 8
Observe that this way we always end up with a rectangle, whose area, the sum of the areas of the squares, is the product of two adjacent Fibonacci numbers:
\latex{s_n=f_1^2+f_2^2+f_3^2+\dots+f_n^2=f_n\times f_{n+1}}.
Solution II
It is worth computing the sum for a few different \latex{ n: }
\latex{s_1=1^2=1\times1},
\latex{s_2=1^2+1^2=2=1\times2},
\latex{s_3=1^2+1^2+2^2=6=2\times3},
\latex{s_4=1^2+1^2+2^2+3^2=15=3\times5},
\latex{s_5=1^2+1^2+2^2+3^2+5^2=40=5\times8}.
Using this, we conjecture that
\latex{s_n=f_n\times f_{n+1}.}
The conjecture is true for \latex{n = 1} (and, of course, for \latex{ 2;\, 3;\, 4;\, 5 }). Suppose that it is true for \latex{ n } and then prove that it is also true for \latex{n + 1}.
\latex{f_1^2+f_2^2+f_3^2+\dots+f_n^2+f_{n+1}^2=f_n\times f_{n+1}+f_{n+1}^2=\\=f_{n+1}\times(f_{n}+f_{n+1})=f_{n+1}\times f_{n+2}.}
We have proved with induction that the proposition is true for every \latex{ n }.
Example 5
Prove that every fourth term of the Fibonacci sequence is divisible by \latex{ 3 }.
Solution
Take a look at the remainders of the terms after dividing by \latex{ 3 }. The sequence of the remainders can be formed similarly to the Fibonacci sequence, the first two terms are \latex{ 1 } and then every term is the remainder of dividing the sum of the two terms directly before it by \latex{ 3 }:
\latex{\text{1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1,}\dots}
The \latex{ 4 }th and \latex{ 8 }th term of the resulting remainder sequence are \latex{ 0 }, that is, the \latex{ 4 }th and 8th terms of the Fibonacci sequence are divisible by \latex{ 3 }. After the \latex{ 8 }th term two adjacent \latex{ 1s } follow again. Since two adjacent terms unambiguously define the remaining terms of the sequence, starting from the \latex{ 9 }th term the sequence of remainders repeats itself with a period of length \latex{ 8 }. It follows then that every fourth term of the Fibonacci sequence is divisible by \latex{ 3 }.
Interestingly, it is not known whether there are infinitely many primes among the terms of the Fibonacci sequence or only finitely many.
The primes among the first \latex{ 10 } terms are: \latex{f_3 = 2}, \latex{f_4 = 3}, \latex{f_5 = 5}, \latex{f_7 = 13}.
The primes among the first \latex{ 10 } terms are: \latex{f_3 = 2}, \latex{f_4 = 3}, \latex{f_5 = 5}, \latex{f_7 = 13}.
Example 6
The sequence \latex{(a_n)} is defined as follows:
\latex{a_1 = 1}, \latex{a_2 = 2}, and for every integer \latex{n \geq1}, \latex{a_n + 2 = 3 × a_n + 1 – 2 × a_n}.
Express \latex{(a_n)} in terms of \latex{ n }.
Solution I
Compute an for the first few values of \latex{ n: }
\latex{a_1=1},
\latex{a_2=2},
\latex{a_3=4},
\latex{a_4=8},
\latex{a_5=16},
\latex{a_5=32}.
By observing these values we can conjecture that \latex{a_n = 2^{n – 1}}. Let's prove it by induction.
The conjecture is true for \latex{n = 1} and \latex{ 2 } since
The conjecture is true for \latex{n = 1} and \latex{ 2 } since
\latex{a_1=2^{1-1}=2^0=1} and \latex{a_2=2^{2-1}=2^1=2}.
Suppose that the conjecture is true for \latex{ n } and \latex{n + 1} and show that it follows for \latex{n + 2}.
By the definition of the sequence, The conjecture is true: the \latex{n^{th}} term of the sequence is \latex{a_n = 2^{n – 1}}.
By the definition of the sequence,
\latex{a_{n+2}=3\times a_{n+1}-2\times a_n=3\times2^n-2\times2^{n-1}=3\times2^n-2^n=2^{n+1}}.
*Solution II
The following idea might help. Rearrange the equation defining a \latex{a_{n+2}} into the form
\latex{a_{n+2}-a_{n+1}=2\times(a_{n+1}-a_n)}.
It follows by repeated applying this that
\latex{a_{n+2}-a_{n+1}=2\times(a_{n+1}-a_n)=\\=2^2\times(a_n-a_{n_1})=\dots=2^n\times(a_2-a_1)=2^n.}
Now take the equations we got for \latex{2,\dots, n} and sum them:
\latex{\begin{array}{rcl}a_n-a_{n-1}=2^{n-2},\\a_{n-1}-a_{n-2}=2^{n-3},\end{array}\\\vdots\\a_3-a_2=2,\\a_2-a_1=1.}
\latex{\overline{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}}
\latex{a_n-a_1=2^{n-2}+2^{n-3}+\dots+2+1=2^{n-1}-1,} from which
\latex{a_n=2^{n-1}.}
*DEFINITION: We say that the sequence (an) is monotonically increasing (decreasing) if for every integer \latex{n \geq 1\;\; a_n + 1 \geq a_n (a_{n + 1} \leq a_n)}.
*DEFINITION: The sequence \latex{(a_n)} is bounded from below (above) if there exists a number K such that for every integer \latex{n \geq 1}, we have \latex{a_n \geq K (a_n \leq K)}. In this case the number K is called a lower (upper) bound of the sequence.
Example 7
Prove that the sequence \latex{a_1=2}, \latex{a_{n+1}=\frac 1 2\times\left(a_n+\frac{2}{a_n}\right)} is monotonically decreasing and bounded from below.
Solution
We can use the following idea to show that the sequence is bounded from below.
It follows from the definition of \latex{a_{n+1}} that since \latex{a_{1}=2\gt 0}, every term of the sequence is positive. We can look at \latex{a_{n+1}} as the arithmetic mean of two numbers and the inequality of arithmetic and geometric means (AM-GM inequality) can be applied to it:
\latex{a_{n+1}=\frac 1 2\times\left(a_n+\frac{2}{a_n}\right)\geq\sqrt{a_n\times\frac 2{a_n}}=\sqrt2}.
Therefore \latex{\sqrt2} is a lower bound of the sequence starting from the second term.
Since \latex{2\gt\sqrt2} it is also true for the first term that it is greater than \latex{\sqrt2}.
Since \latex{2\gt\sqrt2} it is also true for the first term that it is greater than \latex{\sqrt2}.
\latex{ n } order to verify the sequence is monotone decreasing, take a look at the sign of the difference \latex{a_n-a_{n+1}}.
\latex{a_n-a_{n+1}=\frac 12 \times a_n-\frac 1{a_n}=\frac{a_n^2-2}{2\times a_n}\geq0},
since we have already proven that for every integer \latex{n\geq1}, \latex{a_n\geq\sqrt2} and \latex{a_n\gt0}.
Thus the sequence is indeed monotone decreasing.
Thus the sequence is indeed monotone decreasing.
It is possible to show that the nth term of the sequence approximates for large \latex{ n }.
It is worth mentioning the following way of illustrating a sequence: its terms can easily be depicted as points on the graph of the function (Figure 9):
It is worth mentioning the following way of illustrating a sequence: its terms can easily be depicted as points on the graph of the function (Figure 9):
\latex{f(x)=\frac1 2\times\left(x+\frac{2}{x}\right)}, \latex{x\neq0}.
\latex{y=\frac 12\times\left(x+\frac 2 x\right)}
\latex{y=x}
\latex{y=\frac 1 2x}
\latex{ x}
\latex{ 0 }
\latex{ 1}
\latex{ y}
\latex{ 1}
\latex{ 2}
\latex{ 3}
\latex{ 4}
\latex{ 2}
Figure 9
Example 8
Examine the following sequence in terms of monotonicity:
\latex{a_1=\frac 14, \dots,a_{n+1}=p\times a_n\times(1-a_n)}, if \latex{p=1} and \latex{p=2}.
Illustrate the terms of the sequence by using the graph of the function
\latex{f(x)=p\times x\times(1-x)}.
\latex{y=x}
\latex{y=-\left(x-\frac 1 2\right)^2+\frac 1 4}
\latex{\frac 1 4}
\latex{\frac 1 4}
\latex{\frac 1 2}
\latex{ 1 }
\latex{ x }
\latex{ 0 }
\latex{ 1 }
\latex{ y }
Figure 10
Solution
For the case \latex{ p = 1 }, the graph of the function can be seen in Figure 10. It is enough to plot it on the interval \latex{0 \leq x \leq1}. (We marked some of the terms of the sequence too.)
The sequence is monotonically decreasing, since
\latex{a_n-a_{n+1}=a_n-a_n\times(1-a_n)=a_n^2\geq0}.
It can be proven that for large n the terms of the sequence get arbitrarily close to \latex{ 0 }.
\latex{y=x}
\latex{y=2x\times(1-x)}
\latex{\frac 1 4}
\latex{\frac 1 4}
\latex{\frac 1 2}
\latex{ 1 }
\latex{ x }
\latex{ 0 }
\latex{ 1 }
\latex{ y }
Figure 11
In the case \latex{p = 2}, the graph of the function can be seen in Figure 11, plotted for the interval \latex{0 \leq x \leq 1} only. (We marked some of the terms of the sequence as well.)
Let’s prove that the sequence is monotonically increasing. This seems obvious by the illustration. This time compute the difference \latex{a_{n + 1} – a_n}:
Let’s prove that the sequence is monotonically increasing. This seems obvious by the illustration. This time compute the difference \latex{a_{n + 1} – a_n}:
\latex{a_{n+1}-a_{n}=2a_n-2a_n^2-a_n=a_n\times(1-2a_n)}.
This is positive if \latex{a_n \gt 0} and \latex{1 – 2a_n \gt 0}. The second condition means \latex{a_n \lt\frac 12}.
Thus we need to prove that
Thus we need to prove that
\latex{0\lt a_n\lt\frac 12}.
We’ll prove this by induction.
For \latex{a_1=\frac 1 4} the proposition is true. Suppose that \latex{0 \lt a_n \lt \frac 1 2} and then show it follows that \latex{0 \lt a_{n + 1} \lt \frac 1 2}.
\latex{a_{n+1}=2a_n\times(1-a_n)}, and and as both \latex{0 \lt 2a_n} and \latex{0 \lt 1 – a_n}, we can use the AM-GM inequality to deduce
\latex{a_{n+1}=2a_n\times(1-a_n)}, and and as both \latex{0 \lt 2a_n} and \latex{0 \lt 1 – a_n}, we can use the AM-GM inequality to deduce
\latex{2a_n\times(1-a_n)\leq2\times\left(\frac{a_n+a-a_n}{2}\right)^2=\frac1 2},
where equality holds if and only if \latex{a_n =1– a_n}, that is, \latex{a_n = \frac 1 2}, which is not the case.
We have shown that \latex{0 \lt a_{n + 1} \lt \frac 12}, therefore the sequence is monotonically increasing.
We have shown that \latex{0 \lt a_{n + 1} \lt \frac 12}, therefore the sequence is monotonically increasing.
\latex{y=x}
\latex{y=3x\times(1-x)}
\latex{\frac 1 2}
\latex{\frac 1 4}
\latex{\frac 1 2}
\latex{ 1 }
\latex{ x }
\latex{ 0 }
\latex{ 1 }
\latex{ y }
Figure 12
It is worth plotting the graph of \latex{ f } for \latex{p = 3} as well. The graph of the function \latex{f(x)=3x ×(1 -x)} on the interval \latex{0 \leq x \leq 1} and some terms of the sequence can be seen in Figure 12.
It can be shown that for \latex{ p = 3 } the sequence (an) “behaves” in the following way:
\latex{a_{2n}\lt a_{2n+2}\lt \frac 23,\\ a_{2n+1}\gt a_{2n+3}\gt\frac 23}; if \latex{n\geq1} is an integer.
The graph of the function \latex{f(x) = 4x \times(1 – x)}, as well as a few terms of the sequence, are illustrated in Figure 13 for \latex{a_1 =\frac 1 8 }. By deeper analysis it is possible to show that the sequence behaves in a totally irregular way.
\latex{y=x}
\latex{y=4x\times(1-x)}
\latex{\frac 1 2}
\latex{\frac 1 4}
\latex{\frac 1 2}
\latex{\frac 1 8}
\latex{ 1 }
\latex{ x }
\latex{ 0 }
\latex{ 1 }
\latex{ y }
Figure 13
Exercises
{{exercise_number}}. Prove the following properties of the Fibonacci sequence.
- \latex{f_2+f_4+f_6+\dots +f_{2n}=f_{2n+1}-1};
- \latex{f_1\times f_2+f_2\times f_3+f_3\times f_4+\dots+f_{2n-1}\times f_{2n}=f_{2n}^2};
- \latex{f_1\times f_2+f_2\times f_3+f_3\times f_4+\dots+f_{2n}\times f_{2n+1}=f_{2n+1}^2-1}.
{{exercise_number}}. Prove that if \latex{n \gt 1} is an integer, then \latex{f_{n – 1} \times f_{n + 1} – f_n^2 = (– 1)^n}. (Try using induction.)
{{exercise_number}}. We have written down the first \latex{ 10 } rows of Pascal’s triangle and drawn a few “inclined” lines.
What can we say about the sum of the numbers along these “inclined” lines?
Formulate the expression in general and validate the equality. Use the basic property of Pascal’s triangle.
\latex{ 10 }
\latex{ 45 }
\latex{ 120 }
\latex{ 210 }
\latex{ 252 }
\latex{ 210 }
\latex{ 120 }
\latex{ 45 }
\latex{ 10 }
\latex{ 1 }
\latex{ 9 }
\latex{ 36 }
\latex{ 84 }
\latex{ 126 }
\latex{ 126 }
\latex{ 84 }
\latex{ 36 }
\latex{ 9 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 8 }
\latex{ 28 }
\latex{ 56 }
\latex{ 70 }
\latex{ 56 }
\latex{ 28 }
\latex{ 8 }
\latex{ 1 }
\latex{ 1 }
\latex{ 7 }
\latex{ 21 }
\latex{ 35 }
\latex{ 35 }
\latex{ 21 }
\latex{ 7 }
\latex{ 1 }
\latex{ 1 }
\latex{ 6 }
\latex{ 15 }
\latex{ 20 }
\latex{ 15 }
\latex{ 6 }
\latex{ 1 }
\latex{ 1 }
\latex{ 5 }
\latex{ 10 }
\latex{ 10 }
\latex{ 5 }
\latex{ 1 }
\latex{ 1 }
\latex{ 4 }
\latex{ 6 }
\latex{ 4 }
\latex{ 1 }
\latex{ 1 }
\latex{ 3 }
\latex{ 3 }
\latex{ 1 }
\latex{ 1 }
\latex{ 2 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
\latex{ 1 }
{{exercise_number}}. Prove that the following sequence is monotonically increasing and bounded from above.
\latex{a_1=\sqrt2},
\latex{a_{n+1}=\sqrt{2+a_n}}.
\latex{a_{n+1}=\sqrt{2+a_n}}.
Illustrate the sequence using the graph of the function
\latex{f(x)=\sqrt{2+x}}, \latex{x\geq0}.
{{exercise_number}}. Prove that the following sequence is monotonically increasing and bounded from above.
\latex{a_1=\frac{1}2},
\latex{a_{n+1}=\frac{1}2+\frac{a_n^2}2}.
\latex{a_{n+1}=\frac{1}2+\frac{a_n^2}2}.
Illustrate the sequence using the graph of the function
\latex{f(x)=\frac 12+\frac{x^2}2}, \latex{x\in\R}.
