Graphs and Tables - Recurrence Relations

The terms of any sequence that are generated by Recurrence formulae can be easily tabulated and graphed.

The graph of a recurrence relation can provide a visual understanding of the way the sequence behaves. For instance we may be able to see that that terms are always increasing or always decreasing in size. We might see that the terms appear to be approaching a limiting size. We might see the that the sequence starts to become erratic an unpredictable. We might also see that the terms change linearly, or as a quadratic curve, or as some other known form, and this might provide a hint as to a possible explicit form of the sequence. 

The graph could take a number of forms. For example you might use a series of discrete points, or perhaps a histogram, or some other type of graph. The important point to be made is that the graph should highlight  the trend exhibited by the sequence, and so the vertical axis scale may need to be adjusted to see this, particularly if part of the graph climbs or falls rapidly.

Our first example concerns a stockbroker's claim that  $\$200$$200 can be turned into a $\$1000$$1000 in $10$10 months. He claims that he can make $30%$30% a month on the investment, for the cost of $\$35$$35 a month. 

Such a claim seems incredulous, but given the percentage earnings and the monthly fee stated, we can form a recurrence relation as:

$U_{n+1}=1.3U_n-35,U_1=200$Un+1​=1.3Un​−35,U1​=200

Note that the coefficient $1.3$1.3 is equivalent to $130%$130%, which is a $30%$30% increase on the previous month's amount as shown by the formula. The subtraction of $\$35$$35 represents the monthly fee. 

We can tabulate the size of the investment at the beginning of the month for the first 10 months as follows, using month numbers and rounded whole dollars: 

The beginning of month $2$2 shows that the investment has grown to $\$225$$225, determined using the recurrence formula, so that $U_2=1.3\times200-35=225$U2​=1.3×200−35=225. Similarly, the beginning of month $3$3 is determined as $U_3=1.3\times225-35=257.50$U3​=1.3×225−35=257.50 which, rounded to whole dollars, becomes $\$258$$258.

The sequence of $10$10 months can be graphed using a 3-dimensional histogram as follows:

Note the monotonic increase in the original investment, with the rate of change in value increasing as well. Although not strictly geometric (the $\$35$$35 deduction effects the ratio between successive terms), the trend is certainly apparent - the higher the amount, the faster it grows. This type of growth is typical of recurrence relationships that have the form $U_{n+1}=r\times U_n\pm k$Un+1​=r×Un​±k with $r>1$r>1. 

Note that had the monthly fee been higher, it may have affected the efficacy of the claim.

Our second example is related to the Fibonacci sequence. Recall that each new term of the Fibonacci sequence, apart from the first two terms, is generated by adding the previous two terms, so that the sequence begins $1,1,2,3,5,8,13,21,...$1,1,2,3,5,8,13,21,... In our example we are going to develop a new sequence where each new term is formed by a subtraction of the two previous terms so that the recurrence formula becomes:

$U_{n+2}=U_{n+1}-U_{n,}U_1=1,U_2=1$Un+2​=Un+1​−Un,​U1​=1,U2​=1

So here, $u_3=u_2-u_1=1-1=0$u3​=u2​−u1​=1−1=0, and $u_4=u_3-u_2=0-1=-1$u4​=u3​−u2​=0−1=−1, and again $u_5=u_4-u_3=-1-0=-1$u5​=u4​−u3​=−1−0=−1 and so on, so our tabulated sequence for the first eight terms are:

  The pattern continues indefinitely, and below is a two-dimensional histogram for the first fourteen terms.

Worked Examples

QUESTION 1

QUESTION 2

QUESTION 3