Sum of a sequence

Algebra Level 5

A sequence $\left \{ p_n \right \}$ is defined by $p_0=5$ , $p_1=5$ , $p_2=-20$ and the following relationship:

$20p_{n+3}+37p_{n+2}+37p_{n+1}+19p_n=0$ for all $n \ge 0$

Find the sum of all terms of this sequence, that is $\displaystyle S=\sum_{n=0}^{\infty} p_n$ , and give your answer as $\lfloor 10000000S \rfloor$ , where $\lfloor \cdot \rfloor$ denotes the floor function .

Hint: the next term of the sequence is $p_3=23$ .

Inspiration (the original version)

The answer is 31415929.

5 solutions

Patrick Corn
May 6, 2019

If the sum converges to $S,$ then summing both sides from $0$ to $\infty$ yields $20(S+10) + 37(S-10) + 37(S-5) + 19S = 0,$ which gives $S = 355/113,$ so the answer is $31415929.$

It is not obvious to me that the series converges, but a computer check shows that the roots of the characteristic equation $20r^3+37r^2+37r+19 = 0$ all have complex absolute value less than $1,$ so I guess it does.

Thank you for your solution and methodology.

I had the answer. Then, the Brilliant system decided that I had looked at the answer. I do not like being cheated in this manner.

I summed 50 million term to get a total of 3.14159292035401.

A Former Brilliant Member - 2 years, 1 month ago

Great solution! A small typo - your $133$ should be $113$ .

Your guess is also correct. It's enough that all three roots have absolute value less than $1$ . If the roots of that cubic are $t,u,v$ , then $p_n=At^n+ Bu^n+Cv^n$ for some constants $A,B,C$ , and the sum of this converges termwise.

As it happens, the absolute values of the roots were chosen to be close to $1$ , so the convergence is slow.

Chris Lewis - 2 years, 1 month ago

Thanks, changed the typo.

Patrick Corn - 2 years, 1 month ago

Mark Hennings
May 6, 2019

The roots $\alpha,\beta\,\gamma$ of the cubic $F(X) \; = \; 20X^3 + 37X^2 + 37X + 19 \; = \; 0$ all have modulus less than $1$ . To see this note that $F(-1) = -1 < 0 < F(-0.95)$ , so that $-1 < \alpha < -0.95$ . The other two roots of $F(X)$ are complex, and hence $|\beta|^2 = |\gamma|^2 = \tfrac{19}{20|\alpha|} < \tfrac{19}{20 \times 0.95} = 1$ . This means that the series $S = \sum_{n \ge 0}p_n$ converges.

We can find constants $A,B,C$ such that $p_n \; = \; A\alpha^n + B\beta^n + C\gamma^n \hspace{2cm} n \ge 0$ and hence $S \; = \; \frac{A}{1-\alpha} + \frac{B}{1-\beta} + \frac{C}{1-\gamma}$ Since $X^3 + 37X^2 + 37X + 19 \; = \; (X-1)(20X^2 + 57X + 94) + 113$ we deduce that $\frac{1}{1-\alpha} \; = \; \tfrac{1}{113}(20\alpha^2 + 57\alpha +94)$ with similar identities for $(1-\beta)^{-1}$ and $(1-\gamma)^{-1}$ . Thus $\begin{aligned} S & = \; \tfrac{1}{113}\big[A(20\alpha^2 + 57\alpha +94) + B(20\beta^2 + 57\beta +94) + C(20\gamma^2 + 57\gamma +94)\big] \\ & = \; \tfrac{1}{113}(20p_2 + 57p_1 + 94p_0) \; =\; \tfrac{355}{113} \end{aligned}$ making $\lfloor 10^7S\rfloor = \boxed{31415929}$ .

K T
Sep 1, 2019

Provided that this sum converges, (and if it doesn't, there is no finite answer) we can sum the whole expression: $\sum_{n=0}^{\infty} (20p_{n+3}+37 p_{n+2}+37 p_{n+1}+ 19p_{n})=0$

$20 \sum_{n=3}^{\infty} p_{n}+ 37\sum_{n=2}^{\infty} p_{n}+37 \sum_{n=1}^{\infty} p_{n}+ 19\sum_{n=0}^{\infty}p_{n}=0$

$20(S-p_0-p_1-p_2)+ 37(S-p_0-p_1)+37 (S-p_0)+ 19S=0$

$S= \frac{355}{113}=3.14159292...$

$\left \lfloor 10^7 S \right \rfloor =\boxed{ 31415929}$

That's how I did it.

Razzi Masroor - 1 year, 4 months ago

Kyle T
May 7, 2019

<?php
$terms = array(5,5,-20);
do {
    //compute next term
    $p_n2 = $terms[count($terms)-1];
    $p_n1 = $terms[count($terms)-2];
    $p_n0 = $terms[count($terms)-3];
    $terms[] = (37*$p_n2 + 37*$p_n1 + 19*$p_n0)/-20;
} while(count($terms)<100000);
$sum = array_sum($terms); //3.1415929... its pi!
echo floor(10000000*$sum); //answer: 31415929
?>

It's not $\pi$ ! But it's close. (Check the units digit of the answer)

Some follow-up questions (These seem best handled with coding, so I'm going to defer to you, or any other interested programmer)

How many terms are needed to guarantee the required accuracy?
Within "reasonable constraints" on the parameters (ie the initial terms and coefficients - these constraints could be, say, all of them are integers and none is greater than $50$ in absolute value), what's the worst case for the number of terms needed?

Chris Lewis - 2 years, 1 month ago

To answer that first one, how many terms until we guarantee required accuracy: I reworked my code and got 6010. Need someone to double check that though. I kept adding terms until floor(10000000*$sum)==31415929.
I dont understand the second one though?

Kyle T - 2 years, 1 month ago

Thanks for the reply! The question is, is $6009$ the largest number of terms that doesn't give a rounded total of $31415929$ ? The values of the partial sums $S_n$ oscillate above and below the eventual value of $S_{\infty}=\frac{355}{113}$ .

The second question is somewhat harder - basically, if your aim is to make convergence to the limit $\frac{355}{113}$ as slow as possible (but still have the series converge), how should you tweak the parameters?

Chris Lewis - 2 years, 1 month ago

A Former Brilliant Member
May 6, 2019

By summing the recurrance relation from n=0 to infinity we get $p_3$ + $p_4$ +....=1485/113=13.141592920354. Therefore the required sum is 13.14159292035+5+5-20=3.141592920354.

Sum of a sequence

The answer is 31415929.

5 solutions

0 pending reports