This is a question from the book Discrete Mathematical Structures by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross.
I want to find the explicit formula of the following recursive formula using backtracking: $$C_n = C_{n-1} + n$$
The initial condition is $c_1 = 4$.
-
$C_n = C_{n-1} + n$
$C_{n-1} = C_{(n-1)-1} = C_{n-2} + n$
-
$C_n = C_{n-2} + n + n$
$C_{n-2} = C_{(n-2)-1} = C_{n-3} + n$
-
$C_n = C_{n-3} + n + n + n$
$$\therefore C_n = C_{n-(n-1)} + n(n-1)$$
$$= C_1 + n^2 – n$$
$$= n^2 – n + 4$$
However, the answer in the book is $3 + \frac{n(n+1)}{2}$
Edit: I was wrongly substituting. I corrected the error but I am still not getting the answer.
-
$C_n = C_{n-1} + n$
$C_{n-1} = C_{(n-1)-1} + (n-1) = C_{n-2} + n – 1$
-
$C_n = C_{n-2} + n – 1 + n = C_{n-2} + 2n – 1$
$C_{n-2} = C_{(n-2)-1} + (n – 2) = C_{n-3} + n – 2$
-
$C_n = C_{n-3} + n – 2 + 2n – 1 = C_{n-3} + 3n – 3$
0, 1, 3, … are triangular numbers.
$$\therefore C_n = C_{n-(n-1)} + n(n-1) – \frac{n(n+1)}{2}$$
Simplifying this does not give the answer. Where is the mistake?
Best Answer
$$C_n = C_{n-1} + n = (C_{n-2} + n-1) + n = C_{n-3} + (n-2) + (n-1) + n = \dots = C_1 + 2 + 3 + \dots + n = 4 + 2 + 3 + \dots + n = 3 + (1 + 2 + 3 + \dots + n) = 3 + \frac {n(n+1)} 2 .$$
Alternatively, you may note that
$$C_n - C_1 = (C_n - C_{n-1}) + (C_{n-1} - C_{n-2}) + \dots + (C_2 - C_1) = n + (n-1) + \dots + 2 = \frac {n (n+1)} 2 - 1,$$
whence $C_n = C_1 - 1 + \frac {n (n+1)} 2 = 3 + \frac {n (n+1)} 2$.