Double Trouble

Since we must have $x_0 \le 5$ , $x_1 \le 11$ , $x_2 \le 24$ and $x_3 \le 50$ , the number of ways is $\sum_{a=1}^5\left(\sum_{b=2a+1}^{11}\left(\sum_{c=2b+1}^{24} \left(\sum_{d=2c+1}^{50} 1 \right)\right)\right) \; = \; 2170$ This can either be computed by brute force/computer or by using the formulae for $\sum_{r=1}^n r$ , $\sum_{r=1}^n r^2$ and $\sum_{r=1}^n r^3$ .

Relevant wiki: Recursive functions

Define the following function:

• $N_n(i) =$ The number of ways you can pick $x_0$ to $x_n$ such that $x_n < i+1$

Then,

• $N_0(i) = i$
• $N_n(i) = 0$ if $i < 2^{n+1} - 1$
• $N_n(i) = N_n(i-1) + N_{n-1}({\lfloor{\frac{i-1}{2}}\rfloor})$ otherwise

These were derived as follows...

The first equation follows trivially.

The second one I got by looking at the minimum value possible for $x_n$ .

• The minimum $x_0$ is clearly $1$ .
• The minimum $x_1$ is $2 \times x_0 + 1 = 3$ .
• The minimum $x_2$ is $2 \times x_1 + 1 = 7$ .

And so the general expression for these minima is:

$x_{n,min} = 2^{n+1} - 1$

So anything less than these minima must be $0$ .

So,

$N_n(i) = 0$ if $i < 2^{n+1} - 1$

Finally, the third equation I got by looking at how many ways you could pick $x_0$ to $x_n$ for $x_n < i + 1$ . This will be equal to the number of ways that they can be picked for $x_n < i$ which is given by $N_n(i-1)$ plus the number of "new" combinations you can now make with the new maximum $x_n$ , which is given by $N_{n-1}({\lfloor{\frac{i-1}{2}}\rfloor})$ . The floor function was needed only to differentiate between even and odd numbers.

So, $N_n(i) = N_n(i-1) + N_{n-1}({\lfloor{\frac{i-1}{2}}\rfloor})$ otherwise

Solving, you find:

$N_3(50) = \boxed{2170}$

Or if you prefer the compute intensive, brute force, way (in perl):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

$n = 0;

for $a (1..50) {
        for $b (1..50) {
                for $c (1..50) {
                        for $d (1..50) {
                                if  ($b > 2 * $a && $c > 2 * $b && $d > 2 * $c) {
                                        $n ++
                                }
                        }
                }
        }
}

print "$n\n";

Output:

$\boxed{2170}$