Converting Java Code to Mathematic formula

Question

I have algorithm , but I don't know how to convert it to mathematic formula.

public static Integer calculate(Integer n){
    if (n==1 ) return 2;
    else if(n==2) return (2*n+3);
    else if(n>=3){
        int temp=3;
        int sum=2*n+3;
        for (int i=0;i<n-2;i++)
        {
            sum=sum+(2*temp+3);
            temp=2*temp+3;
        }
        return sum;
    }
    return 0;

}

Any kind of tips is appreciated. Results depending on inputs

1: 2
2: 7
3: 18
4: 41
5: 88

Thanks

Answer 1

Lets look at the code for $n \ge 3$ first:

int temp=3;
int sum=2*n+3;
for (int i=0;i<n-2;i++) {
    sum=sum+(2*temp+3);
    temp=2*temp+3;
}
return sum;

Using mathematical notation, this is equivalent to:

\begin{align} t_0 &= 3 \\ s_0 &= 2n +3 \\ s_n &= s_0 + \sum_{i=0}^{n-3} 2 t_i + 3 \\ t_{i+1} &= 2 t_i + 3 \end{align} Note the recurrence for the $t_i$: $$ t_0 = 3 \\ t_{i+1} = 2 t_i + 3 $$ It is an inhomogenous linear recurrence. We note $$ t_{i+2} = 2 t_{i+1} + 3 $$ and subtract to get a homogenous linear recurrence: $$ t_{i+2} - t_{i+1} = 2(t_{i+1} - t_i) \iff \\ t_{i+2} = 3 t_{i+1} - 2 t_i \iff \\ t_n = 3 t_{n-1} - 2 t_{n-2} $$ This last recurrence $t_n = 3 t_{n-1} - 2 t_{n-2}$ has the characteristic polynomial $$ p(t) = t^2 - 3 t + 2 = (t - 3/2)^2 - 9/4 + 8/4 = (t -3/2)^2 -1/4 $$ which has the roots $$ t = (3 \pm 1)/2 \in \{ 1, 2 \} $$ This means the solution is $$ t_n = k_1 1^n + k_2 2^n = k_1 + k_2 2^n $$ Applying $t_0 = 3$ and $t_1 = 2\,3+3 = 9$ give $$ 3 = k_1 + k_2 \quad 9 = k_1 + 2 k_2 $$ or $$ 3 = k_1 + k_2 \quad 6 = k_2 $$ or $$ k_1 = -3 \quad k_2 = 6 $$ and $$ t_i = 6 \, 2^i - 3 $$ So for the sum we have \begin{align} s_n &= s_0 + \sum_{i=0}^{n-3} 2 t_i + 3 \\ &= 2n + 3 + \sum_{i=0}^{n-3} 2 (6 \, 2^i - 3) + 3 \\ &= 2n + 3 + \sum_{i=0}^{n-3} 12 \, 2^i - 3 \\ &= 2n + 3 - 3(n-2) + 12 \sum_{i=0}^{n-3} 2^i \\ &= 9 - n + 12 \frac{2^{n-2} - 1}{2 - 1} \\ &= 9 - n + 12 (2^{n-2} - 1) \\ &= 3 \, 2^n - n - 3 \end{align} which used the formula for a geometric series for $q = 2$.

This gives the case distinction \begin{align} f(n) &= \begin{cases} 2 & \text{for } n = 1 \\ 2n+3 & \text{for } n = 2 \\ s_n & \text{for } n \ge 3 \\ 0 & \text{otherwise} \end{cases} \\ &= \begin{cases} s_1 & \text{for } n = 1 \\ s_2 & \text{for } n = 2 \\ s_n & \text{for } n \ge 3 \\ 0 & \text{otherwise} \end{cases} \\ &= \begin{cases} s_n & \text{for } n \ge 1 \\ 0 & \text{otherwise} \end{cases} \\ &= \begin{cases} 3 \, 2^n - n - 3 & \text{for } n \ge 1 \\ 0 & \text{otherwise} \end{cases} \end{align} where $f$ should return the same values as calculate.

Answer 2

The formula is $$3 \times 2^n - n-3$$

This is easily proved by induction.

How did I come up with that formula? Well, the successive terms are basically doubling (if we go up to $n=10$, the ratio is down to $2.007$), so it's definitely of the form $2^n$. But these numbers are actually much too small: if we divide the whole sequence through by $2^n$ we get a sequence which is tending to 3 fairly fast. So it's probably of the form $3 \times 2^n$.

Now, if we just look at the two sequences side by side, it's easy to see that there's just a linear difference between them, and it turns out to be $n-3$.

---

Alternatively, you could magically intuit or work out the answer by looking at the code, but that's a bit magical.

The sum over $i$ is actually not involving $i$ at all, so it simply represents "do this thing $n-2$ times". Notice that we're only adding temp(i+1) to the sum each time, so we could rephrase as

temp = 2*temp + 3;
sum += temp

What is the $n$th value of temp? The recurrence $x_{n+1} = 2x_n+3$ with $x_0 = 3$ has solution $$x_n = 3 \times (2^{n+1}-1)$$ so we're essentially just summing $3 \times (2^{n+1}-1)$ as $n$ ranges from $1$ to $n-2$, with a starting offset of $2n+3$. That sum is just what I said it is at the start.