Summation of $(((2N+1).2 + 1).2 + 1)\cdots $

Question

Is there a way to sum up this series:

$(((2N+1).2 + 1).2 + 1)\cdots $

The actual question that I encountered was on a coding site (HackerRank) where it said that you had a tree which grows twice in an year. Starting from the Monsoon cycle where the height doubles of what it is ($2N$) and then in the winters it adds 1 meter to its height. So for any given number of cycles $C$, find the resultant height.

This could be done easily given that we had an expression that can represent the summation to a finite number instead of the normal loop over all method.

Plus, can this be said to be an arithmetico-geometric series?

Answer 1

Sum up to 1st term $=2N+1$

Sum up to 2nd term $=(2N+1)2+1=4N+3=2^2N+2^2-1$

Sum up to 3rd term $=(4N+3)2+1=8N+7=2^3N+2^3-1$

$\cdots$

So by observation, sum up to $m$th term $$2^m\cdot N+2^m-1$$ where integer $m\ge1$

which can be easily validated by induction

Answer 2

This is a recurrence relationship where

$$\begin{cases} u_n=2u_{n-1}+1\\ u_0=N \end{cases}$$

Assume that $$u_n=Ar^n+B $$

Then solve for $A, r, B$ using $u_0, u_1, u_2$to give $$u_n=(N+1)\cdot 2^n-1$$