Section6.5Recurrence sequences
Exercise 5.2.4 We use the notation as follows 1: the largest disk, 2: the second largest disk, 3: the second smallest disk, 4: the smallest disk. At the beginning there are 4 disks on peg \(A\text{,}\) it is denoted as \(\halmaz{1,2,3,4}\text{,}\) while peg \(B\) and peg \(C\) has no disks at all, so we write \(\halmaz{}\text{.}\)
# move peg \(A\) peg \(B\) peg \(C\) 0 \(\halmaz{ 1, 2, 3, 4 }\) \(\halmaz{}\) \(\halmaz{}\) 1 \(\halmaz{ 1, 2, 3 }\) \(\halmaz{ 4 }\) \(\halmaz{}\) 2 \(\halmaz{ 1, 2 }\) \(\halmaz{ 4 }\) \(\halmaz{ 3 }\) 3 \(\halmaz{ 1, 2 }\) \(\halmaz{}\) \(\halmaz{ 3, 4 }\) 4 \(\halmaz{ 1 }\) \(\halmaz{ 2 }\) \(\halmaz{ 3, 4 }\) 5 \(\halmaz{ 1, 4 }\) \(\halmaz{ 2 }\) \(\halmaz{ 3 }\) 6 \(\halmaz{ 1, 4 }\) \(\halmaz{ 2, 3 }\) \(\halmaz{}\) 7 \(\halmaz{ 1 }\) \(\halmaz{ 2, 3, 4 }\) \(\halmaz{}\) 8 \(\halmaz{}\) \(\halmaz{ 2, 3, 4 }\) \(\halmaz{ 1 }\) 9 \(\halmaz{}\) \(\halmaz{ 2, 3 }\) \(\halmaz{ 1, 4 }\) 10 \(\halmaz{ 3 }\) \(\halmaz{ 2 }\) \(\halmaz{ 1, 4 }\) 11 \(\halmaz{ 3, 4 }\) \(\halmaz{ 2 }\) \(\halmaz{ 1 }\) 12 \(\halmaz{ 3, 4 }\) \(\halmaz{ }\) \(\halmaz{ 1, 2 }\) 13 \(\halmaz{ 3 }\) \(\halmaz{ 4 }\) \(\halmaz{ 1, 2 }\) 14 \(\halmaz{ }\) \(\halmaz{ 4 }\) \(\halmaz{ 1, 2, 3 }\) 15 \(\halmaz{ }\) \(\halmaz{ }\) \(\halmaz{ 1, 2, 3, 4 }\) -
Exercise 5.2.5 The idea is to determine geometric progressions satisfying the same recurrence relation as \(a_n\text{.}\) Let \(g_n\) be a geometric progression with the above mentioned property such that \(g_n=g_0r^n\) for some \(g_0\) and \(r\text{.}\) It follows that
\begin{equation*} r^2=7r-10\Rightarrow r^2-7r+10=0\text{.} \end{equation*}Solving the quadratic equation yields that \(r=2\) or 5. We obtained two appropriate progressions and we know that linear combinations of these progressions satisfy exactly the same recurrence. Define \(W_n\) as follows
\begin{equation*} W_n=s\cdot 2^n+t\cdot 5^n\text{.} \end{equation*}We try to fix \(s\) and \(t\) such that \(W_0=a_0\) and \(W_1=a_1\text{.}\) We get that
\begin{align*} \amp W_0=a_0=0,\\ \amp W_1=a_1=2\text{.} \end{align*}Therefore
\begin{align*} s+t\amp =0,\\ 2s+5t\amp =2\text{.} \end{align*}The solution of the above system of equations is \(s=-2/3, t=2/3\text{.}\) Hence
\begin{equation*} a_n=W_n=-\frac{2}{3}\cdot 2^n+\frac{2}{3}\cdot 5^n\text{.} \end{equation*} -
Exercise 5.2.6 Let \(g_n\) be a geometric progression satisfying the same recurrence relation as \(a_n\) such that \(g_n=g_0r^n\) for some \(g_0\) and \(r\text{.}\) We have that
\begin{equation*} r^2=4r-3\Rightarrow r^2-4r+3=0\text{.} \end{equation*}That is, \(r\in\halmaz{1,3}\text{.}\) The linear combination we consider now is
\begin{equation*} W_n=s\cdot 1^n+t\cdot 3^n=s+t\cdot 3^n\text{.} \end{equation*}The additional conditions imply that
\begin{align*} \amp W_0=a_0=1,\\ \amp W_1=a_1=13\text{.} \end{align*}Therefore
\begin{align*} s+t\amp =1,\\ s+3t\amp =13\text{.} \end{align*}We get the solution \(s=-5,t=6\text{.}\) The explicit formula for \(a_n\) is
\begin{equation*} -5+6\cdot 3^n\text{.} \end{equation*} -
Exercise 5.2.7 This is an example of an order 3 linear recurrence. We define \(g_n=g_0r^n\) for some \(g_0\) and \(r\text{,}\) which is a geometric progression. We assume that it satisfies the same recurrence relation as \(a_n\text{,}\) that is, we obtain
\begin{equation*} r^3=-2r^2+r+2\text{.} \end{equation*}It is a cubic polynomial. We look for integer solutions. If there is an integral root, then it divides 2. Hence the possible integral roots are \(\pm 2,\pm 1\text{.}\)
The cubic polynomial \(r^3+2r^2-r-2\) can be written as \(\left(x-1\right) \cdot \left(x+1\right) \cdot \left(x+2\right)\text{,}\) that is, there are three integral roots. In this case we have three geometric progressions satisfying the recurrence, therefore the appropriate linear combination is \begin{equation*} W_n=s\cdot (-2)^n+t\cdot (-1)^n+u\cdot 1^n\text{.} \end{equation*}\(r\) \(r^3+2r^2-r-2\) -2 0 -1 0 1 0 2 12 The corresponding system of linear equations is
\begin{align*} s+t+u\amp =0,\\ -2s-t+u\amp =1,\\ 4s+t+u\amp =2\text{.} \end{align*}We subtract the first equation from the third one to get \(3s=2\text{.}\) So we have that \(s=2/3\text{.}\) We eliminate \(s\) from the first two equations
\begin{align*} t+u\amp =-\frac{2}{3},\\ -t+u\amp =\frac{7}{3}\text{.} \end{align*}It is easy to see that \(u=5/6\) and \(t=-3/2\text{.}\) The explicit formula for \(a_n\) is
\begin{equation*} \frac23 \cdot (-2)^n-\frac32\cdot (-1)^n+\frac56\text{.} \end{equation*} -
Exercise 5.2.8 The solution is similar to the previous one, so we only provide some details of the computation. The cubic polynomial in this case is
\begin{equation*} r^3-6r^2+11r-6\text{.} \end{equation*}
The three roots of the equation are 1, 2 and 3. Let \(W_n=s\cdot 1^n+t\cdot 2^n+u\cdot 3^n\text{.}\) The initial values should be equal as well, hence \begin{align*} s+t+u\amp =0,\\ s+2t+3u\amp =0,\\ s+4t+9u\amp =1\text{.} \end{align*}\(r\) \(r^3-6r^2+11r-6\) \(-6\) \(-504\) \(-3\) \(-120\) \(-2\) \(-60\) \(-1\) \(-24\) \(1\) \(0\) \(2\) \(0\) \(3\) \(0\) \(6\) \(60\) It is easy to eliminate \(s\) from the second and the third equation
\begin{align*} t+2u\amp =0,\\ 3t+8u\amp =1\text{.} \end{align*}Therefore \(u=1/2, t=-1\) and \(s=1/2\text{.}\) We obtain the following explicit formula
\begin{equation*} a_n=\frac{1}{2}-2^n+\frac{1}{2}\cdot 3^n\text{.} \end{equation*} -
Exercise 5.2.9 In this exercise we have an order 2 recurrence sequence. Following the method we described we get a quadratic polynomial
\begin{equation*} r^2-4r+4=(r-2)^2\text{.} \end{equation*}It has only a multiple root, so we have to consider the linear combinations of \(2^n\) and \(n\cdot 2^n\text{.}\) That is,
\begin{equation*} W_n=s\cdot 2^n+tn\cdot 2^n\text{.} \end{equation*}The initial values of \(a_n\) are \(a_0=-1\) and \(a_1=0\text{,}\) hence the system of linear equations is
\begin{align*} s\amp =-1,\\ 2s+2t\amp =0\text{.} \end{align*}It is clear that \(s=-1\) and \(t=1\text{.}\) Thus the closed-form formula for \(a_n\) is
\begin{equation*} -2^n+n\cdot 2^n\text{.} \end{equation*} -
Exercise 5.2.10 As before we reduce the problem to a polynomial equation, which is
\begin{equation*} r^3-5r^2+3r+9\text{.} \end{equation*}There are 6 possible integral roots, the divisors of 9, that is, \(\halmaz{\pm 9,\pm 3,\pm 1}\text{.}\)
We obtained only 2 roots of the cubic polynomial. Dividing the polynomial \(r^3-5r^2+3r+9\) by \((r+1)\cdot (r-3)\) we get \(r-3\) and the remainder is 0. That means that \begin{equation*} r^3-5r^2+3r+9=(r+1)\cdot (r-3)^2\text{.} \end{equation*}\(r\) \(r^3-5r^2+3r+9\) \(-9\) \(-1152\) \(-3\) \(-72\) \(-1\) \(0\) \(1\) \(8\) \(3\) \(0\) \(9\) \(360\) There is a double root, so \(W_n\) is defined as
\begin{equation*} s\cdot (-1)^n+t\cdot 3^n+un\cdot 3^n\text{.} \end{equation*}Substituting \(n=0,1,2\) yields
\begin{align*} s+t\amp =3,\\ -s+3t+3u\amp =4,\\ s+9t+18u\amp =29\text{.} \end{align*}Using that \(s=3-t\) we obtain
\begin{align*} 4t+3u\amp =7,\\ 8t+18u\amp =26\text{.} \end{align*}So we have the solution \(s=2,t=1\) and \(u=1\text{.}\) The explicit formula for \(a_n\) is given by
\begin{equation*} 2\cdot (-1)^n+3^n+n\cdot 3^n\text{.} \end{equation*} -
Exercise 5.2.11 Consider the sequence
\begin{equation*} u_n=\left(\frac{5-3\sqrt{5}}{2}\right)^n+\left(\frac{5+3\sqrt{5}}{2}\right)^n, n\geq 0\text{.} \end{equation*}We have \(u_0=2\) and \(u_1=5\text{.}\) We try to find a second order linear recurrence satisfied by \(u_n\text{.}\) If there is such a recurrence, then the corresponding quadratic polynomial is
\begin{equation*} \left(r-\frac{5-3\sqrt{5}}{2}\right)\cdot \left(r-\frac{5+3\sqrt{5}}{2}\right)=r^2-5r-5\text{.} \end{equation*}Therefore the possible recurrence relation is
\begin{equation*} u_n=5u_{n-1}+5u_{n-2}=5\cdot (u_{n-1}+u_{n-2})\text{.} \end{equation*}Now we have that \(u_n\) is an integer for all \(n\) and \(u_n\) is a multiple of 5 if \(n\geq 1\text{.}\)
-
Exercise 5.2.12 We have a sequence
\begin{equation*} u_n=(4-\sqrt{3})^n+(4+\sqrt{3})^n, n\geq 0\text{.} \end{equation*}One computes that \(u_0=2\) and \(u_1=8\text{,}\) that is, the first two elements of the sequence is divisible by 2. The quadratic polynomial
\begin{equation*} \left(r-4+\sqrt{2}\right)\cdot \left(r-4-\sqrt{2}\right)=r^2-8r+14 \end{equation*}is the polynomial corresponding to the appropriate recurrence relation. Hence the recurrence sequence is given by
\begin{align*} u_0\amp =2,\\ u_1\amp =8,\\ u_n\amp =8u_{n-1}-14u_{n-2} n\geq 2\text{.} \end{align*}The statement follows easily since \(u_0=2\cdot 1, u_1=2\cdot 4\) and \(u_n=2\cdot(4u_{n-1}-7u_{n-2})\text{.}\)