Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

3.2: Recognising Sequences

[ "article:topic", "Fibonacci Numbers", "authorname:thangarajahp", "Fibonacci Sequences", "Triangular numbers", "Harmonic sequences", "license:ccbyncsa", "showtoc:yes" ]
  • Page ID
    4899
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    For some of the sequences we can predict the \(n^{th} \) term easily, and the explicit (general)  formula can be checked using induction. In this section we will explore this kind of sequences.

    Example \(\PageIndex{1}\): Harmonic sequence

    Find a formula for the \(n^{th}\) term of the a sequence that has the following initial terms: \(\displaystyle \frac{1}{2}, \displaystyle\frac{1}{3},  \displaystyle\frac{1}{4},  \displaystyle\frac{1}{5}, \displaystyle\frac{1}{6}, \cdots\).

    Answer:

    \(\displaystyle\frac{1}{n+1}\)

     

    Caution

    Two sequences may start with the same initial terms but diverge later on.

    Example \(\PageIndex{2}\): One's

    \(1 \times 11=11\)

    \(11 \times 11=121\)

    \(111 \times 111=12321\)

    \(1111 \times 1111=1234321\)

    Can you predict the pattern?

    Example \(\PageIndex{3}\): Perfect Squares

    Find a formula for the \(n^{th}\) term of the following sequence \(1,4,9,16,25,\cdots\).

    Answer:

    \( n^2\).

    Here is another way to find the \(n^{th}\) term:

    Note that the difference in the sequence \(1,4,9,16,25,\cdots\) is \(3,5,7,9,\cdots\) and the difference in this sequence is \(2\). Therefore the \(n^{th}\) can be written as a quadratic formulae \(pn^2+qn+c\). \(p,q,c\) can be found using the following information:

      \(t_n\) \(d_n=t_n-t_{(n-1)}\) \(d=d_n-d_{(n-1)}\)
    n=1 p+q+c    
    n=2 4p+2q+c 3p+q  

    n=3

    9p+3q+c 5p+q 2p
    n=4 16p+4q+c 7p+q 2p
           

    Hence, in our case, \(2p=2\). Therefore, \(p=1\). Now \(3p+q=3 \) and \(p=2\). Thus \(q=0\). Now \(p+q+c=1\), which implies \(c=0\). Hence, \(t_n=n^2\).

    Quadratic Sequences:

    A sequence is called quadratic sequence if the differences of consecutive terms, \( d_n=t_n−t_{(n−1)} \) differ by the same amount \(d=d_n−d_{(n−1)}, \forall n \in  \bf{N} \). In this case, the \(n^{th}\) term of the sequence is given by

    \(t_n= a+(n-1) d_1+(n-1)(n-2)\frac{d}{2}\),

    where \(d_1\) is the first difference between first term and the second term of the sequence, and \(d\) is the common second difference. This result can be shown by using induction.

    Below is another way to solve:

    Example \(\PageIndex{4}\):  Quadratic Sequences

    Find a formula for the \(n^{th}\) term of the following sequence: \(2,6,12,20,\cdots\)

    2      6      12        20

      4       6           8

           2          2  

    Hence  the \(n^{th}\) term has a term   \((2/2) n^2.\)

    \(t_n\) 2 6 12 20
    \(n^2\) 1 4 9 16
    \(n^2-t_n \) 1 2 3 4

     Notice that \(n^2-t_n \) is an arithmetic sequence with the first term \(1\) and the common difference is \(1\).  Thus \(n^2-t_n =1+1(n-1)\). Hence \(t_n=n^2-n.\)

     

    Triangular numbers

     

    Thinking Out Loud:

    \(1, 3, 6, 10, 15, 21, 28, ...\) are triangular numbers: you can arrange them in a triangular array:

    \(T_n = n\)th triangular number. What is the hundredth triangular number?

    Example \(\PageIndex{5}\): Hexagonal Tilling (Centered hexagonal numbers)

    Find the \(n^{th}\) term of the sequence \(1,7,19, 37, \cdots\).

    By Incnis Mrsi (Own work) [CC0], via Wikimedia Commons

    There are 6 triangular numbers and 1 center, Therefore  

    \(6  \frac{(n -1)(n)}{2} + 1 = 3(n -1)(n) + 1 = 3(n2 -n) + 1 = 3n2 -3n + 1 . \)

    Example \(\PageIndex{6}\):

    Consider the sequence of tilling using hexagons. The hexagon numbers are the sequence 1, 6, 15, · · · . Predict the nth term. Explain your prediction.



     
       

     

     

     

    A.

    Term # (n)

    1

    2

    3

    4

    B.

    # of hexagons

    1

    6

    15

    28

    C.

    B/A

    1

    3

    5

    7

    D.

    2(n)-1

    1

    3

    5

    7

     

    C = 2n-1

    Since we know that (A)C = B, we can conclude that term number (A)=n, multiplied by C (2n-1) will give you the corresponding number in the sequence (B).


    Therefore: \( t_n =  n(2n-1) = 2n^2-n\)


     

    Tower of Hanoi

    According to the legend of the Tower of Hanoi (formerly the "Tower of Brahma" in a temple in the Indian city of Benares), the temple priests are to transfer a tower consisting of 64 fragile disks of gold from one part of the temple to another, one disk at a time. The disks are arranged in order, no two of them the same size, with the largest on the bottom and the smallest on top. Because of their fragility, a larger disk may never be placed on a smaller one, and there is only one intermediate location where disks can be temporarily placed. It is said that before the priests complete their task the temple will crumble into dust and the world will vanish in a clap of thunder. 

     

    Let A, B and C be the posts. Then 
     
    1 disk: 1 move

    Move 1: move disk 1 to post C

    2 disks: 3 moves

      Move 1: move disk 2 to post B
    Move 2: move disk 1 to post C
    Move 3: move disk 2 to post C

    3 disks: 7 moves

       Move 1: move disk 3 to post C
    Move 2: move disk 2 to post B
    Move 3: move disk 3 to post B
    Move 4: move disk 1 to post C
    Move 5: move disk 3 to post A
    Move 6: move disk 2 to post C
    Move 7: move disk 3 to post C

    The number of moves needed to transfer n disks from post A to post C is \(2M+1\), where \(M\) is the number of moves needed to transfer \(n-1\) disks from post A to post C . This is called recursive sequence.  Can we able to guess a formula depending on n only?

    Number of Disks         Min. number of  Moves
            1                                           1
            2                                           3
            3                                          7
            4                                        15
            5                                        31 

    From this pattern, we can guess the formula for finding the minimum number of moves it takes to transfer n disks from post A to post C is: \(2^n - 1.\) This guess can be proved by using induction.

    Recursive Sequences

    Definition

    A recurrence relation for a sequence  \(\{a_n\}\) is  formula that relates to each term \(a_n\) to  its predecessors \(a_0,a_1, \cdots, a_{n-1}\).

     

    Thinking Out Loud:

    A tiling consists of covering a region using tile pieces from some given set so that the region is completely covered without overlaps. How many ways can you arrange the 2 x 1 dominoes to cover 2 x n checker-board?

     

    Fibonacci Sequences

     

    By Ein_Hase_mit_blauem_Ei.svg: MichaelFrey & Sundance Raphael derivative work: HB (Ein_Hase_mit_blauem_Ei.svg) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0) or GFDL (http://www.gnu.org/copyleft/fdl.html)], via Wikimedia Commons

    Fibonacci sequence: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, , ...\)

    Let \(F_n = n\)\(th\) Fibonacci Number.The \(n\) term in the Fibonacci sequence is obtained by adding the previous two terms. 

    That is, \(F_n = F\)\((n - 1)\) \(+ \, F\)\((n - 2)\), \(n > 2, \, F_1=1, \) and \( F_2 = 1\)

    Some facts about Fibonacci sequence :

    • The sum of the first n even numbered Fibonacci numbers is one less than the next Fibonacci number.
    • The only square Fibonacci numbers are 0, 1 and 144.
    • The sum of the first n odd numbered Fibonacci numbers is the next Fibonacci number.

    Example \(\PageIndex{9}\):

    Consider the Fibonacci sequence: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, , ...\)

    The squares of the Fibonacci sequence: \( 1,1 ,4,9, 25, 64, 169 ....\). Consider the sum of the squares of consecutive terms, F2\((n - 1)\) \(+ \, F^2\)\((n - 2)\),  for \( n >2\).  That is:

    1+1=2

    1+4 =5

    4+9=13

    What can you say about the resulting number?

    Answer:

    It is Fibonacci. In fact, \(F_{(2n-3)} = F^2\)\((n - 1)\) \(+ \, F^2\)\((n - 2)\).

     

     

     

     

    Example \(\PageIndex{11}\):  More Fibonacci IMG_20170301_081722_picmonkeyed (1).jpg

    Let \(a_n\)  be the Fibonacci sequence. That is \(a_n=a_{n-1}+a_{n-2}, n \in \mathbb{N}, \mbox{ with } a_1=1,a_0=0\), where \( \mathbb{N}\) be the set of all natural numbers.
    Consider the Fibonacci squares illustrated in figure:

    Let \(h_n\) be  the shortest (perpendicular) distance between \(n^{th}\) parallel diagonal vectors. Consider the figure:

    Comparing the the area of trapezoids, we get

     \(h_n=\displaystyle\frac{a_n^2-a_{n-1}^2} {\sqrt{2}(a_n-a_{n-1})} =\displaystyle\frac{1}{\sqrt{2}}\left(a_n+a_{n-1}\right).\)
    Hence, \(h_n\) is Fibonacci like sequence.

     

    Hexagonal numbers by Incnis Mrsi (Own work) [CC0], via Wikimedia Commons

    Tower of Hanoi by André Karwath aka Aka (Own work) [CC BY-SA 2.5 (https://creativecommons.org/licenses/by-sa/2.5)], via Wikimedia Commons 

    Finacci Rabits  By Ein_Hase_mit_blauem_Ei.svg: MichaelFrey & Sundance Raphael derivative work: HB (Ein_Hase_mit_blauem_Ei.svg) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0) or GFDL (http://www.gnu.org/copyleft/fdl.html)], via Wikimedia Commons