The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.