Questions:
(a) What's $a_5$?
(b) Find a formula for $a_n$ in terms of $a_{n - 1}$
(c) Find a formula for $a_n$ in terms of $n$ and use (b) to prove your formula
The $n$th term of the given sequence is the number of line segments in an $n$-cube.
Playing around with the given sequence we can discover the following:
$a_0 = 2^{-1} \times 0 = 0 \\ a_1 = 2^{1 - 1} \times 1 = 1 \\ a_2 = 2^{2 - 1} \times 2 = 4 \\ a_3 = 2^{3 - 1} \times 3 = 12 \\ a_4 = 2^{4 - 1} \times 4 = 32 \\ a_5 = 2^{5 - 1} \times 5 = 80 \\ \ldots \\ a_n = 2^{n - 1} \times n$
The formula above solves (a) and (c) partially. Although, I think we could just use induction to prove it. I am having hard time finding the first order recurrence relation for $a_n.$ How do we find it? Also, how do we go about finding recurrence relations in general?
$\endgroup$1 Answer
$\begingroup$Since your formula so far involves powers of $2$, look for a recurrence that involves doubling.
To get from $0$ to $1$, we double and then add $1$.
To get from $1$ to $4$, we double and then add $2$.
To get from $4$ to $12$, we double and then add $4$.
Continue doing this, until you see the pattern.
$\endgroup$ 1
