5.3 Getting Information from Difference Equations

This section is about the use of the inductive paradigm in the analysis of difference equations. Continuing with several examples from the previous section, we will guess or otherwise concoct closed forms and then prove them correct by induction. We also show that you can often establish very useful information even when you can t find a closed form. As we explained in Section 5.1, the approaches illustrated in this section are important because many difference equations cannot be solved by the systematic methods of later sections. Even when those systematic methods apply, the approaches of this section are sometimes faster.

Example 1

Conjecture and prove an explicit formula for E _n , the expected length of sequential search from Example 3, Section 5.2.

Solution In Section 5.2 we showed that E ₁=1 and

From this equation it is easy to compute

from which we guess

We will now prove this equality by induction. Let P(n) be the assertion that the guess is correct for the particular value n. We already know that P(1) is true. Assuming P( n ?1) and substituting in Eq. (1), we have

Even when you can t guess an explicit formula for a series by computing values from its difference equation, you can still use the difference equation to prove a formula if you discover it by some other means. For instance, for the geometric series we showed (Example 2, Section 5.2)...