(a) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ : $$a_k = \frac12 a_{k- 1} + \frac12 a_{k+1 }$$(b) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ : $$a_k = 1+\frac12 a_{k- 1} + \frac12 a_{k+1 }$$.
Problem
Source: XIX Kyiv Mathematical Festival 2020 1.1
Tags: recurrence relation, Sequence, algebra
30.11.2020 01:15
Nice exercise for characteristic polynomials. Part $a$ We take the characteristic polynomial $2t=1+t^2$, to get that the only root is $t=1$, then we have that $a_k=A.(1)^k+B.k.(1)^k=A+Bk$ Set $k=0$, to get that $A=0$, and then just set $k=100$ to get that $B=\frac{1}{100}$. Thus we have that $a_k=\frac{k}{100}$ Part $b$ This time we consider the following system which we get directly from the recurrence relation: $$2a_{k+1}=2+a_k+a_{k+2}$$$$2a_k=2+a_{k-1}+a_{k+1}$$now we just subtract to get that $3a_{k+1}-3a_k=a_{k+2}-a_{k-1}$, this translates to the polynomial $3t^2-3t=t^3-1$. This implies that $t=1$, which means that $a_k=A+Bk.(1)^k+Ck^2.(1)^k=A+Bk+Ck^2$. Set $k=0$ to get that $A=0$. Set $k=100$ to get that $B=\frac{1}{100}-100C$, then we plug in the definitions that we have into $2a_{k+1}=2+a_{k}+a_{k+2}$ , we easily get that $C=-1$, from which we have that $B=\frac{100^2+1}{100}$ Thus $a_k=\frac{100^2+1}{100}k-k^2$
30.11.2020 01:28
very nice solution!
30.11.2020 01:47
a) $a_k-a_{k-1}=a_{k+1}-a_k=c$ So $a_{100}=(a_{100}-a_{99})+(a_{99}-a_{98})+...+(a_1-a_0)+a_0=100c \to c=\frac{1}{100}, a_i=\frac{i}{100}$ b) $a_k-a_{k-1}=2+a_{k+1}-a_k$ $a_k-a_{k-1}+2k=a_{k+1}-a_k+2(k+1)=c$ $100c=\sum_{k=0}^{99} (a_{k+1}-a_k+2(k+1))=a_{100}-a_0+ 2\sum_0^{100}k=101*100+1 \to c=101+\frac{1}{100}$ $ic=\sum_{k=0}^{i-1} (a_{k+1}-a_k+2(k+1))=a_{i}-a_0+ 2\sum_0^{i} k=a_i+i(i+1)$ $a_i=ic-i(i+1)=101i+\frac{i}{100}-i^2-i=100i+\frac{i}{100}-i^2$
30.11.2020 01:51
more nice solution!