$k=1$ with $1$ cells. During day $k=2,3,\ldots$ the organism produces $\frac{k^2}{k-1}$ times more new cells than it produced on day $k-1$. Give a simplified expression for the total of all its cells after $n$ days. Hint: This is different to the number of new cells produced during day $n.$
-
- Every day, a builder lays 2 more bricks than the total amount of bricks laid in the last 2 days. Express the number of bricks laid a day as a recursive formula.
- Simplify
$\sum_{k=2}^n (\frac{1}{k} - \frac{1}{k-1})$.
-
Try to formulate the number of new cells each day as a recurrence.
-
Can you write your recurrence relationship as a non-recursive expression?
-
The total number of cells on any day is the sum of the number of cells produced by the organism up to that day.
-
Rearrange
$k\cdot k!$into a difference between 2 factorials.
-
Denote with
$N_k$the number of cells grown at step$k$. We have the recurrence$N_k=\frac{k^2}{k-1}\,N_{k-1},$which we can expand as$$ =\frac{k^2}{k-1}\cdot\frac{(k-1)^2}{k-2}\,N_{k-2} \\ =\frac{k^2}{k-1}\cdot\frac{(k-1)^2}{k-2}\cdot\frac{(k-2)^2}{k-3}\,N_{k-3},$$where we notice successive terms simplify, hence in the end we get:$$N_k = k^2 \cdot (k-1) \cdots 1=k \cdot k!.$$The total number of cells is thus
$$\sum_{k=1}^n k\cdot k!= \sum_{k=1}^n (k+1-1)k! = \sum_{k=1}^n (k+1)! - \sum_{k=1}^n k!,$$where all the terms except the largest and smallest cancel each other leaving$(n+1)!-1$.