# Find a first order recurrence relation for $0, 1, 4, 12, 32,\ldots$

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?

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$.
• Then the recurrence should be $a_n = 2a_{n - 1} + 2^{n - 1}.$ Using the solution above, we get $a_n = 2 \times 2^{n - 2} \times (n - 1) + 2^{n - 1} = 2^{n - 1}(n - 1) + 2^{n - 1} = 2^{n - 1}(n - 1 + 1) = 2^{n - 1}\times n.$ Thanks. – user474507 Oct 12 '17 at 23:03