Interesting Sequence

By observing the first few $a_n$ , $a_1 = 0$ , $a_2 = 3$ , $a_3 = 8$ , $a_4 = 15$ . We note that $a_n = n^2 - 1$ . Let us prove by induction that it is true for all $n \ge 1$ .

1. $a_1 = 1^2 - 1 = 0$ . So, it is true for $n = 1$ .

2. Assume that it is true for $n$ , then:

$\begin{aligned} \quad \quad a_{n+1} & = \color{#3D99F6}{a_n} + 1 + 2\sqrt{1+\color{#3D99F6}{a_n} } \\ & = \color{#3D99F6}{n^2 - 1} + 1 + 2\sqrt{1+\color{#3D99F6}{n^2 - 1}} \\ & = n^2 + 2n \\ & = (n+1)^2 - 2n - 1 + 2n \\ & = (n+1)^2-1 \quad \quad \color{#3D99F6} {\text{So it is true for n+1 too.}} \end{aligned}$

Therefore $a_n = n^2 -1$ is true for all $n \quad \Rightarrow a_{2009} = 2009^2 - 1 = \boxed{4036080}$

Lets define a new sequence $k_i=a_i+1$ by the given equation we know $a_{i+1}+1=a_i+1+2\sqrt{a_i+1}+1=\left(\sqrt{k+1}+1\right)^2$ Replacing the old sequence with the new one: $k_{i+1}=\left(\sqrt{k_{i}}+1\right)^2\\ k_{i+1}=\left(\sqrt{\left(\sqrt{k_{i-1}}+1\right)^2}+1\right)^2=\left(\sqrt{k_{i-1}}+2\right)^2\\ k_{i+1}=\left(\sqrt{k_{i-1}}+2\right)^2=\left(\sqrt{k_{i-2}}+3\right)^2=\cdots\cdots=\left(\sqrt{k_{1}}+i\right)^2\\ a_1=0\Longrightarrow k_1=a_1+1=1\\ k_{i+1}=(1+i)^2\Longrightarrow a_{i+1}=(1+i)^2-1\\ a_{2009}=2009^2-1=\boxed{4036080}$ note:i is not the imaginary unit but a variable here.

By investigating the sequence for some terms it comes as $a_n=n^2 -1$ now simply put n=2009 and thats it!!.

Looking at the sequence as 0,3, 8. 15, 24,....We assume that an = pn^2 +qn + r, and we must find the constants p, q, and r. From n=1, we have 0=p+q+r, n=2, we have 3= 4p+2q+r, and for n=3, 8=9p+3q+r. By elimination we find p=1,q=0, and r=-1. So an = n^2 - 1. The value of a2009 = 2009^2 - 1= 4036080.