1
$\begingroup$

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$
4
$\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
    $\begingroup$ 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. $\endgroup$ – user474507 Oct 12 '17 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.