1

Given that $$a_n = 2a_{n-1} - a_{n-2} - 2$$ for $1<n<50$ and $a_0 = 0$ and $a_{50} = a_{49} + 1$. Find $a_{17}$

I am able to solve 2nd order homogenous recurrence equation to get $a_n = Cn + D$ but I am stuck with the constant term. I cant seem to find the particular solution. Is there another way?

Pooty Lim
  • 101
  • If you know $a_n = Cn + D$ then $a_{50} - a_{49} = C = 1$. Then $D = 0$. So the sequence should be $a_n = n$. But then we have $n = 2(n - 1) - (n - 2) - 2 = 2n - 2 - n + 2 - 2 = n - 2$. – Mark Saving Aug 15 '21 at 21:55
  • Do you mean $1 < n \leq 50$? Otherwise, the equation $a_{50} = a_{49} + 1$ is irrelevant. – Mark Saving Aug 15 '21 at 22:30
  • The 2nd order recurrence must have two independent solutions. What is the second? – user58697 Aug 15 '21 at 22:34
  • A particular solution is $-n^2$. Given the solution for the homogeneous equation $Cn+D$, we can find this particular solution either by undetermined coefficients or by variation of parameters. – GEdgar Aug 15 '21 at 23:00
  • Note that it suffices to solve the thing numerically, as only $a_{17}$ is called for. It's not difficult to find $a_1$ which forces $a_{50}=a_{49}+1$. – lulu Aug 15 '21 at 23:18

2 Answers2

0

I assume the constraint holds for $1 < n \leq 50$, since otherwise, the equation $a_{50} = a_{49} + 1$ tells us nothing at all.

Define $A(x) = \sum\limits_{n = 0}^{50} a_n x^n$.

Then $a_n x^n = (2 a_{n - 1} - a_{n - 2} - 2) x^n$. Summing both sides from $n = 2$ to $n = 50$ gives

$\begin{equation} \begin{split} A(x) - a_1 x - a_0 &= \sum\limits_{n = 2}^{50} a_n x^n \\ &= \sum\limits_{n = 2}^{50} (2 a_{n - 1} - a_{n - 2} - 2) x^n \\ &= (2x\sum\limits_{n = 2}^{50} a_{n - 1} x^{n - 1}) - (x^2 \sum\limits_{n = 2}^{50} a_{n - 2} x^{n - 2}) - (2 \sum\limits_{n = 2}^{50} x^n) \\ &= (2x\sum\limits_{n = 1}^{49} a_n x^n) - (x^2 \sum\limits_{n = 0}^{48} a_n x^n) - (2 x^2 \sum\limits_{n = 0}^{48} x^n) \\ &= 2x(A(x) - a_{50} x^{50} - a_0) -x^2(A(x) - a_{50}x^{50} - a_{49} x^{49}) -2x^2 Q(x) \end{split} \end{equation}$

Here, $Q(x) = \sum\limits_{n = 0}^{48} x^n$.

Rearranging, plus plugging in $a_0 = 0$, gives us

$$(x^2 - 2x + 1) A(x) = a_{50}(x^2 - 2x)x^{50} + a_{49} x^{51} + a_1 x - 2x^2 Q(x)$$

Now we plug in $x = 1$ to both sides. This gives us $0 = -a_{50} + a_{49} + a_1 - 2 \cdot 49$. Now $a_{50} = a_{49} + 1$. Plugging that in gives us $0 = -1 + a_1 - 2 \cdot 49$. So $a_1 = 2 \cdot 49 + 1 = 99$.

From here, we define $B(x) = \sum\limits_{n = 0}^\infty a_n x^n$. Repeating the previous calculation with limits from $0$ to $\infty$ gives us $B(x) - a_1 x = 2xB(x) - x^2 B(x) - 2x^2 \sum\limits_{n = 0}^\infty x^n$. Since $\sum\limits_{n = 0}^\infty x^n = \frac{1}{1 - x}$, we have

$$B(x) (x^2 - 2x + 1) = B(x) (x - 1)^2 = a_1 x + \frac{2x^2}{x - 1}$$

$$B(x) = \frac{a_1 x}{(x - 1)^2} + \frac{2x^2}{(x - 1)^3}$$

Let us note that
$\begin{equation} \begin{split} \frac{1}{(x - 1)^2} &= -\frac{d}{dx} \frac{1}{x - 1} \\ &= \frac{d}{dx} \frac{1}{1 - x} \\ &= \frac{d}{dx} \sum\limits_{n = 0}^\infty x^n \\ &= \sum\limits_{n = 1}^\infty n x^{n - 1} \\ &= \sum\limits_{n = 0}^\infty (n + 1) x^n \end{split} \end{equation}$

$\begin{equation} \begin{split} \frac{1}{(x - 1)^3} &= -\frac{1}{2} \frac{d}{dx} \frac{1}{(x - 1)^2} \\ &= -\frac{1}{2} \frac{d}{dx} \sum\limits_{n = 0}^\infty (n + 1) x^n \\ &= -\frac{1}{2} \sum\limits_{n = 1}^\infty n (n + 1) x^{n - 1} \\ &= -\frac{1}{2} \sum\limits_{n = 0}^\infty (n + 1)(n + 2) x^n \end{split} \end{equation}$

So $B(x) = (a_1 x \sum\limits_{n = 0}^\infty (n + 1) x^n) - \frac{1}{2} 2x^2 \sum\limits_{n = 0}^\infty (n + 1)(n + 2) x^n$.

From this, we extract

$$a_n = a_1 n - n(n - 1) = n(a_1 + 1 - n) = n(100 - n)$$

Verifying our solution, we see that $a_{50} = 50(100 - 50) = 50^2$ and $a_{49} = 49(100 - 49) = (50 - 1)(50 + 1) = 50^2 - 1$, which confirms our original equation $a_{49} + 1 = a_{50}$. We further verify that $a_0 = 0$. And last of all, we see that

$\begin{equation} \begin{split} 2 a_{n - 1} - a_{n - 2} - 2 &= 2 (n - 1)(100 - (n - 1)) - (n - 2)(100 - (n - 2)) - 2 \\ &= 2(n - 1)(101 - n) - (n - 2)(102 - n) - 2 \\ &= 2(102n - n^2 - 101) - (104n - n^2 - 102) - 2 \\ &= 204n - 2n^2 - 202 - 104n + n^2 + 204 - 2 \\ &= -n^2 + 100n \\ &= n(100 - n) \\ &= a_n \end{split} \end{equation}$

So this is indeed the solution.

Note that we don't actually have to verify the solution if we work in the ring of formal power series (except verifying that $a_{50} = a_{49} + 1$), since in this ring, $x - 1$ is a unit and the rules for computing derivatives hold when discussing formal series. But I though it better to just verify the recurrence explicitly rather than going through the theory of why $B(x)$ must actually be correct.

Then $a_{17} = 17(100 - 17) = 17 \cdot 83 = 1411$

Mark Saving
  • 31,855
0

A nice method for such problems is to introduce $b_n:=a_{n+1}-a_n$. Then immediately one has $$b_n=(2a_n-a_{n-1}-2)-(2a_{n-1}-a_{n-2}-2) = 2b_{n-1}-2b_{n-2}.$$ This reduces the recurrence relation to a homogeneous one, subject to $b_{49}=1$; I leave it to the reader to find the right particular solution. Moreover, one has $$a_{17}=a_0+\sum_{n=0}^{16} (a_{n+1}-a_n) = \sum_{n=0}^{16} b_n,$$ so knowing the solution for $\{b_n\}$ yields the solution for $a_{17}$.

Semiclassical
  • 15,842