Compute the kangaroo sequence Backstory

Disclaimer: May contain made up information about kangaroos.

Kangaroos traverse several stages of development. As they grow older and stronger, they can jump higher and longer, and they can jump more times before they get hungry.

In stage 1, the kangaroo is very little and cannot jump at all. Despite this, is constantly requires nourishment. We can represent a stage 1 kangaroo's activity pattern like this.

o


In stage 2, the kangaroo can make small jumps, but not more than 2 before it gets hungry. We can represent a stage 2 kangaroo's activity pattern like this.

 o o
o o o


After stage 2 the kangaroo improves quickly. In each subsequent stage, the kangaroo can jump a bit higher (1 unit in the graphical representation) and twice as many times. For example, a stage 3 kangaroo's activity pattern looks like this.

  o   o   o   o
 o o o o o o o o
o   o   o   o   o


All that jumping requires energy, so the kangaroo requires nourishment after completing each activity pattern. The exact amount required can be calculated as follows.


Assign each o in the activity pattern of a stage n kangaroo its height, i.e., a number from 1 to n, where 1 corresponds to the ground and n to the highest position.
Compute the sum of all heights in the activity pattern.


For example, a stage 3 kangaroo's activity pattern includes the following heights.

  3   3   3   3
 2 2 2 2 2 2 2 2
1   1   1   1   1


We have five 1's, eight 2's, and four 3's; the sum is 5&middot;1 + 8&middot;2 + 4&middot;3 = 33.

Task

Write a full program or a function that takes a positive integer n as input and prints or returns the nutritional requirements per activity of a stage n kangaroo.

This is code-golf; may the shortest answer in bytes win!

Examples

 1 -&gt;     1
 2 -&gt;     7
 3 -&gt;    33
 4 -&gt;   121
 5 -&gt;   385
 6 -&gt;  1121
 7 -&gt;  3073
 8 -&gt;  8065
 9 -&gt; 20481
10 -&gt; 50689
Coffeescript, 19 bytes

(n)-&gt;(n*n-1&lt;&lt;n-1)+1


Edit: Thanks to Dennis for chopping off 6 bytes!

The formula for generating Kangaroo numbers is this:



Explanation of formula:

The number of 1's in K(n)'s final sum is 2^(n - 1) + 1.

The number of n's in K(n)'s final sum is 2^(n - 1), so the sum of all the n's is n * 2^(n - 1).

The number of any other number (d) in K(n)'s final sum is 2^n, so the sum of all the d's would be d * 2^n.


Thus, the sum of all the other numbers = (T(n) - (n + 1)) * 2^n, where T(n) is the triangle number function (which has the formula T(n) = (n^2 + 1) / 2).

Substituting that in, we get the final sum 

  (((n^2 + 1) / 2) - (n + 1)) * 2^n
= (((n + 1) * n / 2) - (n + 1)) * 2^n
= ((n + 1) * (n - 2) / 2) * 2^n
= 2^(n - 1) * (n + 1) * (n - 2)



When we add together all the sums, we get K(n), which equals

  (2^(n - 1) * (n + 1) * (n - 2)) + (2^(n - 1) + 1) + (n * 2^(n - 1))
= 2^(n - 1) * ((n + 1) * (n - 2) + n + 1) + 1
= 2^(n - 1) * ((n^2 - n - 2) + n + 1) + 1
= 2^(n - 1) * (n^2 - 1) + 1


... which is equal to the formula above.