It Isn't As Hard As It Looks

Number Theory Level 2

The sequence a 0 , a 1 , a 2 , … a_0,a_1,a_2,\dots satisfies a m + n + a m − n = 1 2 ( a 2 m + a 2 n ) a_{m+n} + a_{m-n} = \frac{1}{2}(a_{2m}+a_{2n})

for all non-negative integers with m ≥ n m\geq n . If a 1 = 1 a_1 = 1 , determine the value of a 1995 a_{1995}


The answer is 3980025.

View wiki
Ameya Salankar by Ameya Salankar , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Daniel Liu
Jul 30, 2014

Let P ( m , n ) P(m,n) be the statement a m + n + a m − n = 1 2 ( a 2 m + a 2 n ) a_{m+n}+a_{m-n}=\dfrac{1}{2}(a_{2m}+a_{2n}) .

First off, P ( 0 , 0 ) P(0,0) gives a 0 + a 0 = 1 2 ( a 0 + a 0 ) ⟹ a 0 = 0 a_0+a_0=\dfrac{1}{2}(a_0+a_0)\implies a_0=0

Then, P ( 1 , 0 ) P(1,0) gives a 1 + a 1 = 1 2 ( a 2 + a 0 ) ⟹ a 2 = 4 a_1+a_1=\dfrac{1}{2}(a_2+a_0)\implies a_2=4

Then, P ( m , 0 ) P(m,0) gives a m + a m = 1 2 ( a 2 m + a 0 ) ⟹ a 2 m = 4 a m a_m+a_m=\dfrac{1}{2}(a_{2m}+a_0)\implies a_{2m}=4a_m

Now, P ( m , 1 ) P(m,1) gives a m + 1 + a m − 1 = 1 2 ( a 2 m + a 2 ) ⟹ a m + 1 + a m − 1 = 2 a m + 2 a_{m+1}+a_{m-1}=\dfrac{1}{2}(a_{2m}+a_2)\implies a_{m+1}+a_{m-1}=2a_m+2

So we have the recursive equation a m + 1 = 2 a m − a m − 1 + 2 a_{m+1}=2a_m-a_{m-1}+2

Now we proceed by induction to prove that all a m = m 2 a_m=m^2 .

Base cases: a 0 = 0 a_0=0 and a 1 = 1 a_1=1 .

Now assume a k = k 2 a_k=k^2 and a k − 1 = ( k − 1 ) 2 a_{k-1}=(k-1)^2 . We see that a k + 1 = 2 k 2 − ( k − 1 ) 2 + 2 = k 2 + 2 k + 1 = ( k + 1 ) 2 a_{k+1}=2k^2-(k-1)^2+2=k^2+2k+1=(k+1)^2

Thus, all a m = m 2 a_m=m^2 and our answer is a 1995 = 199 5 2 = 3980025 a_{1995}=1995^2=\boxed{3980025} .

10 Helpful 0 Interesting 1 Brilliant 0 Confused

I did the almost same thing !....but instead of induction i solved the recursion directly

Souryajit Roy - 6 years, 10 months ago

Log in to reply

How did u solve the recursion directly? Can you post ur soln. Here?

Nirmit Tripathii - 6 years, 10 months ago

Log in to reply

I will show here how can you solve the recursion a m + 1 = 2 a m − a m − 1 + 2 ( ∗ ) a_{m+1}=2a_m-a_{m-1}+2\:\:\:\:\:\:\:(*) subject to a 0 = 0 , a_0=0, a 1 = 1 , a_1=1, and a 2 = 4. a_2=4. This recurrence and the initial values can be obtained like it was done by @Daniel Liu in his solution here.
Making m = n − 1 m=n-1 and m = n − 2 m=n-2 into the recurrence relation, where n ≥ 3 , n\geq 3, we obtain a n = 2 a n − 1 − a n − 2 + 2 a_n=2a_{n-1}-a_{n-2}+2 and a n − 1 = 2 a n − 2 − a n − 3 + 2 , a_{n-1}=2a_{n-2}-a_{n-3}+2, respectively. By subtracting the second equation from the first and solving for a n , a_n, we get that a n = 3 a n − 1 − 3 a n − 2 + a n − 3 . a_n=3a_{n-1}-3a_{n-2}+a_{n-3}. The characteristic polynomial of this linear recurrence is ( r − 1 ) 3 . (r-1)^3. Using the results explained in the wiki Linear Recurrence Relations with Repeated Roots, we obtain that a n = c 1 + c 2 n + c 3 n 2 . a_n=c_1+c_2n+c_3 n^2. That is, a n a_n will be the linear combination of the sequences 1 , n , 1, n, and n 2 . n^2. Using the initial conditions we get the equations c 1 = 0 , c_1=0, c 1 + c 2 + c 3 = 1 , c_1+c_2+c_3=1, and c 1 + 2 c 2 + 4 c 3 = 4. c_1+2c_2+4c_3=4. and solving this system of equations we get that c 1 = 0 , c_1=0, c 2 = 0 , c_2=0, and c 3 = 1. c_3=1. Therefore, a n = n 2 . a_n=n^2. The last step would be to show that a n = n 2 a_n=n^2 satisfies ( ∗ ) . (*). So this is the only solution of ( ∗ ) (*) subject to the given initial conditions.

Arturo Presa - 5 years, 4 months ago
Rushikesh Joshi
Jul 27, 2014

series formed is 0, 1, 4, 9, 16, 25.... by putting different values of n and m

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...