[Question]
  [
### 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.
1. 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.
2. 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·1 + 8·2 + 4·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](/questions/tagged/code-golf "show questions tagged 'code-golf'"); may the shortest answer in bytes win!
### Examples
```
 1 ->     1
 2 ->     7
 3 ->    33
 4 ->   121
 5 ->   385
 6 ->  1121
 7 ->  3073
 8 ->  8065
 9 -> 20481
10 -> 50689
```
  
[Answer]
# Coffeescript, 19 bytes
```
(n)->(n*n-1<<n-1)+1
```
Edit: Thanks to Dennis for chopping off 6 bytes!
The formula for generating Kangaroo numbers is this:
[![enter image description here](https://i.stack.imgur.com/P4608.png)](https://i.stack.imgur.com/P4608.png)
## 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.
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 6 bytes
```
²’æ«’‘
```
Uses the formula (*n*2 - 1) 2*n* - 1 + 1 to compute each value. @Qwerp-Derp's was kind enough to provide a [proof](https://codegolf.stackexchange.com/a/96386/6710).
[Try it online!](http://jelly.tryitonline.net/#code=wrLigJnDpsKr4oCZ4oCY&input=&args=MTA) or [Verify all test cases.](http://jelly.tryitonline.net/#code=wrLigJnDpsKr4oCZ4oCYClLFvMOH4oKsJEc&input=&args=MTA)
## Explanation
```
²’æ«’‘  Input: n
²       Square n
 ’      Decrement
  æ«    Bit shift left by
    ’     Decrement of n
     ‘  Increment
```
[Answer]
# Java 7, 35 bytes
```
int c(int n){return(n*n-1<<n-1)+1;}
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 4 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ŒḄ¡S
```
[Try it online!](http://jelly.tryitonline.net/#code=xZLhuITCoVM&input=&args=MTA) or [verify all test cases](http://jelly.tryitonline.net/#code=xZLhuITCucKhUwoxMFLCtcW8w4figqxH&input=).
### How it works
```
ŒḄ¡S  Main link. Argument: n (integer)
ŒḄ    Bounce; turn the list [a, b, ..., y, z] into [a, b, ..., y, z, y, ..., b, a].
      This casts to range, so the first array to be bounced is [1, ..., n].
      For example, 3 gets mapped to [1, 2, 3, 2, 1].
  ¡   Call the preceding atom n times.
      3 -> [1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1]
   S  Compute the sum.
```
[Answer]
# Python 2, ~~25~~ 23 bytes
```
lambda x:(x*x-1<<x-1)+1
```
Used miles's formula.
Thanks to Jonathan Allan for -2 bytes.
[Answer]
# Lua, 105 bytes
```
s=tonumber(arg[1])e=1 for i=1,s>1 and 2^(s-1)or 0 do e=e+1 for j=2,s-1 do e=e+j*2 end e=e+s end print(e)
```
De-golfed:
```
stage = tonumber(arg[1])
energy = 1
for i = 1, stage > 1 and 2 ^ (stage - 1) or 0 do
    energy = energy + 1
    for j = 2, stage - 1 do
        energy = energy + j * 2
    end
    energy = energy + stage
end
print(energy)
```
Entertaining problem!
[Answer]
# [Actually](http://github.com/Mego/Seriously), 8 bytes
```
;²D@D╙*u
```
[Try it online!](http://actually.tryitonline.net/#code=O8KyREBE4pWZKnU&input=Mw)
Explanation:
This simply computes the formula `(n**2 - 1)*(2**(n-1)) + 1`.
```
;²D@D╙*u
;         duplicate n
 ²        square (n**2)
  D       decrement (n**2 - 1)
   @      swap (n)
    D     decrement (n-1)
     ╙    2**(n-1)
      *   product ((n**2 - 1)*(2**(n-1)))
       u  increment ((n**2 - 1)*(2**(n-1))+1)
```
[Answer]
# [GolfScript](//golfscript.com), 11 bytes
```
~.2?(2@(?*)
```
[Try it online!](//golfscript.tryitonline.net#code=fi4yPygyQCg_Kik&input=Mw)
Thanks Martin Ender (8478) for removing 4 bytes.
Explanation:
```
            Implicit input                 ["A"]
~           Eval                           [A]
 .          Duplicate                      [A A]
  2         Push 2                         [A A 2]
   ?        Power                          [A A^2]
    (       Decrement                      [A A^2-1]
     2      Push 2                         [A A^2-1 2]
      @     Rotate three top elements left [A^2-1 2 A]
       (    Decrement                      [A^2-1 2 A-1]
        ?   Power                          [A^2-1 2^(A-1)]
         *  Multiply                       [(A^2-1)*2^(A-1)]
          ) Increment                      [(A^2-1)*2^(A-1)+1]
            Implicit output                []
```
[Answer]
# CJam, 11 bytes
```
ri_2#(\(m<)
```
[Try it Online.](//cjam.aditsu.net#code=ri_2%23(%5C(m%3C)&input=3)
Explanation:
```
r           e# Get token.       ["A"]
 i          e# Integer.         [A]
  _         e# Duplicate.       [A A]
   2#       e# Square.          [A A^2]
     (      e# Decrement.       [A A^2-1]
      \     e# Swap.            [A^2-1 A]
       (    e# Decrement.       [A^2-1 A-1]
        m<  e# Left bitshift.   [(A^2-1)*2^(A-1)]
          ) e# Increment.       [(A^2-1)*2^(A-1)+1]
            e# Implicit output.
```
[Answer]
## Mathematica, 15 bytes
```
(#*#-1)2^#/2+1&
```
There is no bitshift operator, so we need to do the actual exponentiation, but then it's shorter to divide by 2 instead of decrementing the exponent.
[Answer]
# C, 26 bytes
As a macro:
```
#define f(x)-~(x*x-1<<~-x)
```
As a function (27):
```
f(x){return-~(x*x-1<<~-x);}
```
[Answer]
# [05AB1E](http://github.com/Adriandmen/05AB1E), 7 bytes
```
n<¹<o*>
```
[Try it online!](http://05ab1e.tryitonline.net/#code=bjzCuTxvKj4&input=MTA)
**Explanation**
```
n<        # n^2
     *    # *
  ¹<o     # 2^(n-1)
      >   # + 1
```
[Answer]
# C#, 18 bytes
```
n=>(n*n-1<<n-1)+1;
```
Anonymous function based on [Qwerp-Derp](https://codegolf.stackexchange.com/users/49561/qwerp-derp)'s excellent mathematical analysis.
Full program with test cases:
```
using System;
namespace KangarooSequence
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int,int>f= n=>(n*n-1<<n-1)+1;
            //test cases:
            for (int i = 1; i <= 10; i++)
                Console.WriteLine(i + " -> " + f(i));
            /* will display:
            1 -> 1
            2 -> 7
            3 -> 33
            4 -> 121
            5 -> 385
            6 -> 1121
            7 -> 3073
            8 -> 8065
            9 -> 20481
            10 -> 50689
            */
        }
    }
}
```
[Answer]
## Batch, 30 bytes
```
@cmd/cset/a"(%1*%1-1<<%1-1)+1"
```
Well, it beats Java anyway.
[Answer]
# [MATL](http://github.com/lmendo/MATL), 7 bytes
```
UqGqW*Q
```
Uses the formula from other answers.
[Try it online!](http://matl.tryitonline.net/#code=VXFHcVcqUQ&input=Mw)
```
U    % Implicit input. Square
q    % Decrement by 1
G    % Push input again
q    % Decrement by 1
W    % 2 raised to that
*    % Multiply
Q    % Increment by 1. Implicit display 
```
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), 9 bytes
```
2n<mn²<*>
```
I'm surprised there isn't a built-in for `2^n`.
[Try it online!](http://oasis.tryitonline.net/#code=Mm48bW7CsjEtKj4&input=&args=OQ)
### Explanation:
```
2n<m        # 2^(n-1) (why is m exponentiation?)
    n²<     # n^2-1
       *    # (2^(n-1))*(n^2-1)
        >   # (2^(n-1))*(n^2-1)+1
```
[Answer]
## Racket 33 bytes
Using formula explained by @Qwerp-Derp
```
(+(*(expt 2(- n 1))(-(* n n)1))1)
```
Ungolfed: 
```
(define (f n)
  (+ (*(expt 2
            (- n 1))
      (-(* n n)
        1))
    1))
```
Testing: 
```
(for/list((i(range 1 11)))(f i))
```
Output: 
```
'(1 7 33 121 385 1121 3073 8065 20481 50689)
```
[Answer]
# Ruby, 21 bytes
@Qwerp-Derp basically did the heavy lifting.
Because of the precedence in ruby, it seems we need some parens:
```
->(n){(n*n-1<<n-1)+1}
```
[Answer]
# Scala, 23 bytes
```
(n:Int)=>(n*n-1<<n-1)+1
```
Uses bit shift as exponentiation
[Answer]
# Pyth, 8 bytes
```
h.<t*QQt
```
[pyth.herokuapp.com](//pyth.herokuapp.com?code=h.%3Ct%2aQQt&input=3&test_suite_input=1%0A2%0A3)
Explanation:
```
     Q   Input
      Q  Input
    *    Multiply
   t     Decrement
       t Decrement the input
 .<      Left bitshift
h        Increment
```
[Answer]
## R, 26 bytes
Shamelessly applying the formula
```
n=scan();2^(n-1)*(n^2-1)+1
```
[Answer]
# [J](http://jsoftware.com/), 11 bytes
```
1-<:2&*1-*:
```
Based on the same formula found [earlier](https://codegolf.stackexchange.com/a/96382/6710).
[Try it online!](https://tio.run/nexus/j#@5@mYGulYKhrY2WkpmWoq2XFlZqcka@goaOXpmSgqWBnpZCpp2Bo8P8/AA)
## Explanation
```
1-<:2&*1-*:  Input: integer n
         *:  Square n
       1-    Subtract it from 1
  <:         Decrement n
    2&*      Multiply the value 1-n^2 by two n-1 times
1-           Subtract it from 1 and return
```
[Answer]
# Groovy (22 Bytes)
```
{(it--**2-1)*2**it+1}​
```
Does not preserve `n`, but uses the same formula as all others in this competition. Saved 1 byte with decrements, due to needed parenthesis.
## Test
```
(1..10).collect{(it--**2-1)*2**it+1}​
```
> 
> [1, 7, 33, 121, 385, 1121, 3073, 8065, 20481, 50689]
> 
> 
> 
[Answer]
# JS-Forth, 32 bytes
Not super short, but it's shorter than Java. This function pushes the result onto the stack. This requires JS-Forth because I use `<<`.
```
: f dup dup * 1- over 1- << 1+ ;
```
[**Try it online**](https://repl.it/DzVG)
]