## B.5 Proofs of Theorems The following lemma is needed to prove [Theorem B.1](LiB0103.html#1391). Lemma B.1****Suppose we have the homogeneous linear recurrence  If *r*1 is a root of the characteristic equation  then  is a solution to the recurrence. Proof: If, for *i* = *n – k*, …, *n*, we substitute *ri*1 for *ti* in the recurrence, we obtain  Therefore, *rn*1 is a solution to the recurrence. **** Proof of [Theorem B.1](LiB0103.html#1391) It is not hard to see that, for a linear homogeneous recurrence, a constant times any solution and the sum of any two solutions are each solutions to the recurrence. We can therefore apply [Lemma B.1](#ap-bex36) to conclude that, if  are the *k* distinct roots of the characteristic equation, then  where the *ci* terms are arbitrary constants, is a solution to the recurrence. Although we do no show it here, one can prove that these are the only solutions.  Proof of [Theorem B.2](LiB0103.html#1397) We prove the case where the multiplicity *m* equals 2. The case of a larger *m* is a straightforward generalization. Let *r*1 be a root of multiplicity 2. Set  where *q*′ (*r*) means the first derivative. If we subsitute *iri*1 for *ti* in the recurrence, we obtain *u* (*r*1). Therefore, if we can show that *u* (*r*1) = 0, we can conclude that *tn* = *nrn*1 is a solution to the recurrence, and we are done. To this end, we have  Therefore, to show that *u* (*r*1) = 0, we need only show that *p* (*r*1) and *p*′ (*r*1) both equal 0. We show this as follows. Because *r*1 is a solution of multiplicity 2 of the characteristic equation *p* (*r*), there exists a *v* (*r*) such that  Therfore,  and *p* (*r*1) and *p*′ (*r*1) both equal 0. This completes the proof.  Proof of [Theorem B.4](LiB0105.html#1434) We obtain the proof for "big *O*." Proof for Ω and Θ can be established in a similar manner. Because *T* (*n*) ∊ *O* (*f* (*n*) for all *n* such that *n* is a power of *b*, there exist a positive *c*1 and a nonnegative integer *N*1 such that, for *n* > *N*1 and *n* a power of *b*,  For any positive integer *n*, there exists a unique *k* such that  It is possible to show, in the case of a smooth function, that if *b* ≥ 2, then  That is, if this condition holds for 2, it holds for any *b* > 2. Therefore, there exist a positive constant *c*2 and a nonnegative integer *N*2 such that, for *n* > *N*2,  Therefore, if *bk*≥ *N*2,  Because *T* (*n*) and *f* (*n*) are both eventually nondecreasing, there exists an *N*3, such that, for *m* > *n* > *N*3,  Let *r* be so large that  If *n* > *br* and *k* is the value corresponding to *n* in [Inequality B.7](#ap-beqn07), then  Therefore, by [Inequalities B.6](#ap-beqn06), [B.7](#ap-beqn07), [B.8](#ap-beqn08), and [B.9](#ap-beqn09), for *n* > *br*,  which means that