Let there be a recurrence relation , where . Show that for large .
We first show that the above recurrence relation constructs the sum
Now we prove by induction.
Notice that the sum approaches for large .
for large .
Note: the way I found this recurrence relation is by investigating the integral As an exercise, prove that this integral is equivalent to the defined recurrence equation.
Check out my other notes at Proof, Disproof, and Derivation