0

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$.

  1. $C_n = C_{n-1} + n$

    $C_{n-1} = C_{(n-1)-1} = C_{n-2} + n$

  2. $C_n = C_{n-2} + n + n$

    $C_{n-2} = C_{(n-2)-1} = C_{n-3} + n$

  3. $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.

  1. $C_n = C_{n-1} + n$

    $C_{n-1} = C_{(n-1)-1} + (n-1) = C_{n-2} + n - 1$

  2. $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$

  3. $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?

Saiyan
  • 25
  • 1
    Your mistake is on the 2nd line of computation: $C_{n-1} = C_{n-2} + n-1$ instead of $C_{n-1} = C_{n-2} + n$ – Jean Marie Feb 21 '16 at 18:08
  • I corrected this but I am still not getting the answer. – Saiyan Feb 21 '16 at 18:24
  • After the correction, lines 2., 3. and 4. are fine. The mistake is where you mention something about 0,1,3 being triangular numbers (so what?) and then drop the result. In fact, you do not prove anything: you just claim that a certain formula must be true? Why? Just because this is your guess? Recurrences are often found through guessing, and then the guessing proved by induction. Where is the induction step? Your approach simply is not a mathematical argument; it is only a statement ("things are like this"). – Alex M. Feb 21 '16 at 18:49

1 Answers1

3

$$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$.

Alex M.
  • 35,207