# Sequence/Series - Find $a_n$ with only $n$

Is it possible to find a formula of $a_n$ with only $n$ for this sequence/series?

$1 , 24 , 69 , 136 , 225 , 1236 , 2449 , 3864 , 5481 , 7300 , 9321 , 11544 , 13969 , 16596 , 19425 , 22456 ...$

I have another way to show each number how it's made, so if it is impossible I can show what every number actually is.

If you need more numbers I can give.

So is possible? ***I don't know the answer, I just made up this by myself...

EDIT: I don't know if it helps somehow, but this is how I did the numbers: *The numbers are part of the real number. I hope it makes sense... $a_1=01=1 , a_2=01+23=24 , a_3=01+23+45=69 , a_4=01+23+45+67=136 , a_5=01+23+45+67+89=225 , a_6=01+23+45+67+89+1011=1236 , a_7=01+23+45+67+89+1011+1213=2449 , a_8=01+23+45+67+89+1011+1213+1415=3864 , a_9=01+23+45+67+89+1011+1213+1415+1617=5481 , ...$ Is it possible now for someone to think of $a_n$ in terms of $n$?

• Shouldn't this be a math.stackexchange.com question? – ibrahim mahrir Nov 25 '17 at 21:14
• Maybe? I thought it should be here because I saw in this section couple similar questions. Should I post the same question in Mathematics? – TuYu Nov 25 '17 at 21:15

A solution to an easier problem

(This first bit was written before Yuval explained how his sequence is actually computed. I'm leaving it here because it might be of some interest anyway.)

Let's begin by assuming Buffer Over Read's recurrence relation is correct (i.e., that it is indeed satisfied by the sequence Yuval has in mind) -- although in fact it looks to me as if it isn't quite. With that assumption, I'll deal with Yuval's question about finding an explicit expression for $a_n$ in terms of $n$.

(I should say that I'm describing what the answer is, rather than proving all the relevant theorems. So if your reaction is "wait, why should that be true?" then it's probably a good reaction. But it turns out that it is true.)

First, we take our recurrence relation -- in this case $a_{n+3}=a_n−3a_{n+1}+3a_{n+2}$ -- and postulate a solution of the form $a_n=t^n$. This yields a polynomial equation in $t$, whose degree equals the order of the recurrence relation. In this case we get $t^3=1-3t+3t^2$ which I would prefer to write as $(t-1)^3=0$.

Now, for each root of the polynomial -- in this case, the only root is $t=1$ -- we get as many candidate solutions as the number of times the root is repeated -- in this case, three. In the "usual" case where the roots aren't repeated, we have $t^n$ as promised; when there are repeated roots, it turns out that we need to throw in $n\cdot t^n$, $n^2\cdot t^n$, and so on, taking as many of these as there are repetitions of the root. So in this case, where $t=1$ so $t^n\equiv1$, our candidate solutions are $1,n,n^2$.

Now our actual solution will be some linear combination of these candidate solutions -- in this case, some quadratic polynomial. And we can find what linear combination by taking as many known entries in the sequence as we have candidate solutions (i.e., as many as the order of the recurrence); each gives a linear equation relating the coefficients, and these linear equations are always independent; so we can solve them to find the coefficients.

Anyway, it's not a coincidence that this kinda-works for most of Yuval's sequence (he's now edited the question to include how he actually computed it) but we'll need to work harder to solve his actual problem.

(Most of) a solution to the actual problem

OK, so what are we doing here? To compute $a_n$ we take the first $2n$ non-negative integers, concatenate them in pairs, and add up the resulting $n$ numbers. This does a weird discontinuous thing when $n$ passes half a power of 10, because the length of the numbers we're concatenating changes. So here's how it goes.

Write $c(n)$ for the concatenation of $n$ and $n+1$. So if both these numbers have $d$ digits, this equals $(10^d+1)n+1$. Write $m(k)=5\cdot10^{k-1}$, the first $n$ for which $2n$ has $k+1$ digits. As a special-case hack, write $m(0)=0$. Now $a_n=\sum_{0\leq i<n}c(2i)$ which we'll split up by length: $a_n=\sum_k\sum_{0\leq i<n\&m(k-1)\leq i<m(k)}2(10^k+1)i+1$.

Suppose $m(r-1)\leq n<m(r)$. (There's always some $r$ for which this holds.) Then the terms in that sum with $k<r$ have $i$ running from $m(k-1)$ to $m(k)-1$ inclusive; and the last nonzero term has $k=r$ and $i$ runs from $m(r-1)$ to $n$ inclusive.

What do those inner sums look like? Like $\sum_{a\leq i<b}2(10^k+1)i+1$ which equals $(10^k+1)(b(b-1)-a(a-1))+(b-a)$. So we have

$$\sum_{k<r}\left[(10^k+1)(m(k)(m(k)-1)-m(k-1)(m(k-1)-1))+m(k)-m(k-1)\right]+(10^r+1)(n(n-1)-m(r-1)(m(r-1)-1))+n-m(r-1).$$

Before simplifing this further, let's do a sanity check since there's lots of calculation above where I could have made mistakes. Take, say, $n=13$. We have $m(0)=0$, $m(1)=5$, $m(2)=50$ so $r=2$ in this case. So that last sum has only one term, with $k=1$, which equals $(10^1+1)(5\cdot4-0)+(5-0)$; and then the "remainder" term is $(10^2+1)(13\cdot12-5\cdot4)+(13-5)$. We therefore have $11\cdot20+5+101\cdot136+8=13969$. Which is, hooray!, the 13th term in Yuval's sequence. OK, let's see if we can make it less ugly.

First of all, the terms without the $(10^k+1)$ factors all telescope. This isn't surprising -- you should think of the sum as being 00+22+44+66+... + 1+1+1+1+... and these terms are the 1s. So we have $n$ plus the still-slightly-horrifying

$$\sum_{k<r}(10^k+1)(m(k)(m(k)-1)-m(k-1)(m(k-1)-1))+(10^r+1)(n(n-1)-m(r-1)(m(r-1)-1)).$$

Horrible though this is, it's much less work to evaluate it for any given $n$ (at least when $n$ is large) than to do the original calculation. Can we do better? Yes, we can get a perfectly explicit expression in terms of $n$ with no summation signs etc. But it's not going to be pretty. We can replace each $m(k)$ with $5\cdot10^{k-1}$, and then expand out everything inside the summand above, and replace $\sum(a+b+\cdots)$ with $\sum a+\sum b+\cdots$, and all those sums are going to be (finite) geometric progressions, for which there's a closed form. But it'll be a rather ugly closed form unless happy coincidences make lots of things cancel. We'll also need to express $r$ explicitly in terms of $n$, but that's easy: $r=2+\lfloor\log_{10}(n/5)\rfloor$.

Right now I haven't the stamina to do it by hand, nor a computer-algebra system conveniently available to do it for me. I might fill in the details here some time in the next few days ... but if anyone's hoping for something neat and elegant, they're likely to be disappointed.

• I didn't understand some parts of what you wrote, but I added in my post the way I looked at the sequence. Maybe it will help you? – TuYu Nov 25 '17 at 22:03
• Yup. Editing my answer now accordingly. – Gareth McCaughan Nov 25 '17 at 22:14

Edit: This is now wrong. See Gareth's answer.

There might be multiple different solutions, but one such solution might be:

$a(n+3) = a(n) - 3a(n+1) + 3a(n+2) \space for \space n \geq 4$

Assuming the above formula, here's a sample extension of the sequence:

$1, 24, 69, 136, 225, 1236, 2449, 3864, 5481, 7300, 9321, 11544, 13969, 16596, 19425, 22456, 25689, 29124, 32761, 36600, 40641, 44884, 49329, 53976, 58825, 63876, 69129, 74584, 80241, 86100, 92161, 98424, 104889, 111556, 118425, 125496, 132769, 140244, 147921, 155800, 163881, 172164, 180649, 189336, 198225, 207316, 216609, 226104, 235801, 245700, 255801, 266104, 276609, 287316, 298225, 309336, 320649, 332164, 343881, 355800, 367921, 380244, 392769, 405496, 418425, 431556, 444889, 458424, 472161, 486100, 500241, 514584, 529129, 543876, 558825, 573976, 589329, 604884, 620641, 636600, 652761, 669124, 685689, 702456, 719425, 736596, 753969, 771544, 789321, 807300, 825481, 843864, 862449, 881236, 900225, 919416, ...$

• WOW! I'm actually suprised that the formula you wrote is working, and the next numbers you wrote are actually right (didn't check all of them), by the way I'm calculating them... I am really curious how you came to the formula you wrote... But what I really asked is, if it's possible to write $a_n$ with only $n$ and not $a_{n+3} , a_{n+2} , a_{n+1}$ like you did. Maybe I am saying it weird, but for example $a_n=n^2-4n+4$.. – TuYu Nov 25 '17 at 21:00
• I don't understant. What do you mean by what you wrote above? Do you mean that without number 1, you coudn't do that? – TuYu Nov 25 '17 at 21:08
• Given the first term of a sequence, and nothing else except that, you would not have enough information to conclude what the next terms are. – Buffer Over Read Nov 25 '17 at 21:11
• Ok I understand. But can you explain more how you got to $a_{n+3}=a_{n}−3a_{n+1}+3a_{n+2}$ – TuYu Nov 25 '17 at 21:13
• Software, actually. – Buffer Over Read Nov 25 '17 at 21:15