Applications on Recurrence Relations

Ex (1): The number of bacteria in a colony doubles every hour. If a colony begin with five bacteria, how many will be present in n hours?

\begin{array}{l} a_{n} = 2 a_{n - 1} W h e r e a_{n} = # o f b a c t i r i a a t t i m e n, w i t h i n t i a l c o n d i n t i o n a_{0} = 5 \\ \Rightarrow a_{n} = 2 a_{n - 1}, a_{0} = 5 \\ O b s e r v e t h a t a_{1} = 2 a_{0} = 2 * 5 = 10 \\ a_{2} = 2 a_{1} = 2 * 10 = 20 \\ a_{3} = 2 a_{2} = 2 * 20 = 40 \end{array}

\begin{array}{l} E x (2) : a_{n} = 2 a_{n - 1} - a_{n - 2}, a_{0} = 0, a_{1} = 3 \\ 1 - F i n d a_{2}, a_{3}, a_{4} . \\ \Rightarrow a_{2} = 2 a_{1} - a_{0} = 2 (3) - 0 = 6 \\ a_{3} = 2 a_{2} - a_{1} = 2 (6) - 3 = 9 \\ a_{4} = 2 a_{3} - a_{2} = 2 (9) - 6 = 12 \\ 2 - D e t e r m i n e w h e t t h e r a_{n} = 3 n, i s a s o l u t i o n f o r t h i s r e c u r r e n c e r e l a t i o n . \\ \Rightarrow p l u g i n a_{n} = 3 n, i n t h e r e c u r r e n c e r e l a t i o n, \\ a_{n} = 2 a_{n - 1} - a_{n - 2} \\ 3 n d o e s i t e q u a l 2 (3 n - 3) - (3 n - 6) \\ (6 n - 6) - (3 n - 6) = 3 n \\ T h u s a_{n} = 3 n i s a s o l u t i o n o f t h e r e c u r r e n c e r e l a t i o n . \\ 3 - I s a_{n} = 2^{n}, a s o l u t i o n f o r t h i s r e c u r r e n c e r e l a t i o n ? \\ \Rightarrow a_{n} = 2 a_{n - 1} - a_{n - 2} \\ a_{n} = 2^{n} \Rightarrow 2^{n} d o e s i t e q u a l 2 * 2^{n - 1} - 2^{n - 2} \\ 2^{n} - 2^{n - 2} \\ 2^{n} \neq 2^{n} - 2^{n - 2} \\ T h u s a_{n} = 2^{n} i s a s o l u t i o n o f t h e r e c u r r e n c e r e l a t i o n . \end{array}