A wise man told the king to give him one grain of rice one for the first square of a chessboard and for the each remaining square to give him twice the number for the previous square. Thirty-two days later, the king realized that there is not enough rice in all of world to reward him. The number of grains on the *n*th square is given by the recurrence relation *T*(1) = 1 and *T*(*n*) = 2*T*(*n* − 1).

The algebraic equation *x*^{2} = *x* + 2 specifies the value of an unknown real that must be found. The differential equation specifies functions from reals to reals that must be found. Similarly, a recurrence relations like *T*(*n*) = 2 × *T*(*n* − ...

Start Free Trial

No credit card required