Difficult recurrence relation

[Darya]

I have to find a closed form of this recurrence relation. I've never dealt with indexes with 2 parameters. Any clues where to start and what topic I should get familiar with to solve that? Thanks!

 

[Steven G]

Can you figure out what x₀ is? Think what values m and n need to be. Think!

After that I think that letting n=1 would be helpful.

 

[Steven G]

How about m=0 and n=?

 

[Darya]

How about m=0 and n=?

Hi and thanks for your reply!
This sequence is pure pain for me.
[MATH]x_0[/MATH] is of course 0, we can see it from m=1, n=1.
When m=3,n=1, [MATH]x_4+x_2=1/2(x_6+x_2)[/MATH], substituting to m=2, n=1
and m=3,n=0, we get [MATH]x_2=4 [/MATH]I got so far:
[MATH]x_0=0, x_1=1,x_2=4, x_3=9, x_4=16[/MATH]But I have no idea how to get to a closed form. Any references and recommended topics?

Thanks a lot!

 

[Dr.Peterson]

You might just look at those values and make a conjecture, then try to prove it. The numbers 0, 1, 4, 9, 16 look very familiar ...

(Not to say I've even tried to prove that the obvious conjecture is true, but it's certainly the next thing I'd try.)

 

[Darya]

You might just look at those values and make a conjecture, then try to prove it. The numbers 0, 1, 4, 9, 16 look very familiar ...

(Not to say I've even tried to prove that the obvious conjecture is true, but it's certainly the next thing I'd try.)

Omg, got it. Thanks so much!

 

[Dr.Peterson]

It's easy to show that the conjectured formula satisfies the requirements. Did you prove that it is unique? I'd like to see what you did.

 

[Darya]

It's easy to show that the conjectured formula satisfies the requirements. Did you prove that it is unique? I'd like to see what you did.

Of course! I'm a beginner at proofs, I tried to prove it with strong induction.

Conjecture:
Closed form of reccurence sequence [MATH]x_{m+n}+x_{m-n}=1/2(x_{2m}+x_{2n})[/MATH] for m,n∈ N+{0}, m>=n
is: [MATH]x_{k}=k^2[/MATH] for k>=0

Proof:
1. Base case: k=0
Let m=0, n=0, then [MATH]x_{0}=0[/MATH] is the only solution to [MATH]2x_0=x_0[/MATH][MATH]0^2=0[/MATH], holds.

2. By strong induction, assume that formula holds for [MATH]1,2,3..,k-1,k[/MATH], then it has to hold for [MATH]k+1[/MATH].

Let m=k, n=1
[MATH]x_{k+1}=1/2(x_{2k}+x_2)-x_{k-1}[/MATH]Let m=f,n=0
[MATH]x_{2k}=4x_k[/MATH]
Substituting that, [MATH]x_2=4[/MATH], [MATH]x_k=k^2[/MATH] and [MATH]x_{k-1}=(k-1)^2[/MATH],
we get [MATH]x_{k+1}=(k+1)^2[/MATH].

Proven