1

I encountered the following recurrence relation in a problem from the Kangaroo Competition: $$ a_1=1~;~ a_{n+m}=a_n+a_m+n \cdot m ~ (n+m>1) $$ The following values are directly found: $$a_2=a_1+a_1+1 \cdot 1 = 3\\ a_3=a_1+a_2+1 \cdot 2=6\\ a_4=a_1+a_3 +1\cdot 3=a_2+a_2+2 \cdot 2=10 \\ a_5=a_1+a_4+1 \cdot 4=a_2+a_3+2 \cdot 3= 15$$

Is there an elementary proof that this is a well-defined recurrence relation, that is, the right hand side never yields two different values for $a_{n+m}$?

  • 3
    It seems that $a_n = n(n+1)/2$. This leads to an elementary proof. By the way, there seems to be a typo in the first relation $a_{m+n}=...$ in your post. – Gribouillis Nov 07 '21 at 17:03
  • 1
    Use the recurrence for $m=1$ to solve for $a_n$, then verify whether it satisfies the relation for all $m$. – dxiv Nov 07 '21 at 23:10

1 Answers1

2

Following the suggestions made in the comments, if a succession $(a_n)_n$ satisfies the recurrence relation of the question, also it must satisfy $$ a_{n+1}=a_n+a_1+n \cdot 1$$. This gives $a_n=\frac{n(n+1)}{2}$ (arihtmetic progression) and it's an easy computation to show that $$\frac{(n+m)(n+m+1)}{2}= \frac{n(n+1)}{2}+\frac{m(m+1)}{2}+nm$$ so indeed the recurrence relation is well-defined.