The Computer Laboratory

Practice Paper 1 Question 11

An organism is born on day \(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.\)

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. 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.
  2. Simplify \(\sum_{k=2}^n (\frac{1}{k} - \frac{1}{k-1})\).

Hints

  • Hint 1
    Try to formulate the number of new cells each day as a recurrence.
  • Hint 2
    Can you write your recurrence relationship as a non-recursive expression?
  • Hint 3
    The total number of cells on any day is the sum of the number of cells produced by the organism up to that day.
  • Hint 4
    Rearrange \(k\cdot k!\) into a difference between 2 factorials.

Solution

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\).

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.