The Gateway to Computer Science Excellence
0 votes


recurrence  relation

An organism is born on day k = 1 with 1 cells. During day k = 2, 3, . . . the organism produces 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

in Graph Theory by Junior (595 points)
edited by | 66 views
What is k 2 k-1?


1 Answer

0 votes
We can formulate a recurrence relation for this as:

$$T(n) = \frac{n^2}{n-1}T(n-1)$$

Expanding using iterative method,

$$T(n)  = \frac{n^2}{n-1}\times\frac{(n-1)^2}{n-2}\dots\frac{(n-k+1)^2}{n-k}T(n-k)$$.

We have the base case that $T(1) = 1$.

Therefore, $k = n-1$.

Substituting and performing basic manipulations, you should get the answer as $n!n$

So the required answer is now $\sum_{i=1}^{i=n} i \times i!$.

Note that it can be written as $\sum_{i=1}^{i=n} (i +1)i! - i!$ which is a telsecoping sum of the form $(2! - 1!) + (3! - 2!) \dots ((n+1)! - n!)$ giving the answer as $(n+1)! - 1$.
by Loyal (6.8k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
105,275 users