Consider the multiplication of bacteria in a controlled environment. Let ar denote the number of bacteria there are on the r-th day. We denote the rate of growth on the r-th day to be ar- 2(ar- 1). If it is known that the rate of growth doubles every day, determine ar, given that a0= 1
The recurrence formed is $a_{r+1}-4a_{r}+4a_{r-1}=0$
solution is $a_{r}=c*2^r+d*r2^r$
by $a_{0}=1 \implies c=1$
but how to calculate $d$?
Use generating functions. Define $A(z) = \sum_{r \ge 0} a_r z^r$, rewrite your recurrence without subtraction in indices: $$ a_{r + 1} - 4 a_{r + 1} + 4 a_r = 0 $$ Multiply by $z^r$, sum over $r \ge 0$, and recognize the resulting sums: $$ \frac{A(z) - a_0 - a_1 z}{z^2} - 4 \frac{A(z) - a_0}{z} + 4 A(z) = 0 $$ Solve for $A(z9$, write as partial fractions: $$ A(z) = \frac{4 a_0 - a_1}{2 (1 - 2 z)} - \frac{2 a_0 - a_1}{2 (1 - 2 z)^2} $$ By the generalized binomial theorem: \begin{align} a_n &= \frac{4 a_0 - a_1}{2} \cdot 2^n + \frac{2 a_0 - a_1}{2} \cdot \binom{-2}{n} (-2)^n \\ &= \left( \frac{4 a_0 - a_1}{2} + \frac{2 a_0 - a_1}{2} \cdot \binom{n + 2 - 1}{2 - 1} \right) \cdot 2^n \\ &= ((2 a_0 - a_1) n + 6 a_0 - 2 a_1) \cdot 2^{n - 1} \end{align}