## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

### 27 Recurrence Relations

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 nth square is given by the recurrence relation T(1) = 1 and T(n) = 2T(n − 1).

The algebraic equation x2 = 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 − ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required