Try Finding The First Few Terms!

Probability Level 2

$\large a_{i}= 2a_{i-1} -a_{i-2} +2$

Define the sequence ${(a_{n}})$ with intial terms $a_{0} = 0, a_{1} = 1$ , satisfying the recurrence relations above for all $i \geq 2.$ Determine the value of $a_{1000}$ .

The answer is 1000000.

1 solution

Chew-Seong Cheong
Mar 7, 2016

We claim that $a_k = k^2$ for all $k$ and prove it by induction.

1) When $k = 0$ , $a_0 = 0^2 = 0$ and when $k=1$ , $a_1 = 1^2 = 1$ . Therefore, the claim is true for the two initial $k$ .

2) Assuming that $a_k = k^2$ is true for $k \ge 2$ , then we have:

$\begin{aligned} \quad a_k & = 2a_{k-1} - a_{k-2} + 2 \\ \Rightarrow a_{k+1} & = 2a_{k} - a_{k-1} + 2 \\ & = 2k^2 - (k-1)^2 + 2 \\ & = 2k^2 - (k^2-2k+1) + 2 \\ & = k^2 + 2k + 1 \\ & = (k+1)^2 \end{aligned}$

$\quad$ The claim is also true for $k+1$ , therefore the claim is true for all $k$ .

Therefore, $a_{1000} = 1000^2 = \boxed{1000000}$

Did it with a similar approach..

Rishabh Tripathi - 5 years, 3 months ago

Can you add your solution?

Calvin Lin Staff - 5 years, 3 months ago

A very similar point (that maybe it is the same of you, Rishabh) of view could be the following.

1) Every positive square satisfy the formula (it is basically the induction step of Chew-Seong) $2(k-1)^2-(k-2)^2+2= 2k^2+2-4k-k^2+4k-4+2=k^2$

2) Since $a_0$ and $a_1$ are consecutive squares then the sequence must go on with squares

It "surprises" me that actually the sequence works for $k \geq 0$ , and maybe it would be nice to see what happens if one tries to start with non consecutive squares or something like that

Riccardo Moschetti - 5 years, 3 months ago

Check out linear recurrence relations - with repeated roots :)

Calvin Lin Staff - 5 years, 3 months ago

Try Finding The First Few Terms!

The answer is 1000000.

1 solution

0 pending reports