Question

find a formula for general term of the sequence
\[\large 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,\ldots \]

Answer 1

At first I thought maybe we will have to use the math floor and have some thing where we add 1/2, 2/2, 1/3, 2/3, 3/3 kind of thing. But then I thought why not try a generating function? \[\Large S = 1+2x+2x^2+3x^3+3x^4+3x^5+4x^6+... \\ \Large xS=x+2x^2+2x^3+3x^4+3x^5+3x^6+4x^5+... \\ \Large S-xS=1+x+x^3+x^6+x^{10}+...\] Aha! these are just the triangular numbers \[\Large S(1-x)=\sum_{n=0}^\infty x^{\frac{n(n+1)}{2}}\] \[\Large S=\sum_{n=0}^\infty \frac{x^{\frac{n(n+1)}{2}}}{1-x}\] I'm not really sure where to go from here, so invoking the sacred geometric series: \[\Large S=\sum_{n=0}^\infty \sum_{m=0}^\infty x^{\frac{n(n+1)}{2}+m}\] Yeah, I don't know, I haven't played with generating series enough to know what to do with them. lol

Answer 2

Could modular arithmetic be involved?

Answer 3

Wow! that looks like a good start, if i interpret your work correctly we have below explicit formula :

\[\large a_{T_n} = n\]

where \(T_n\) is the \(n\)th triangular number
http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/First_six_triangular_numbers.svg/374px-First_six_triangular_numbers.svg.png

Answer 4

@ospreytriple please feel free to use modular arithmetic/floor functions/ any other cool tricks

Answer 5

Are you asking for help, or wanting us to answer? It's quite easy if you solve a quadratic (based on the formula for triangular numbers) and use the floor function.

Answer 6

will this do
http://www.wolframalpha.com/input/?i=%5Cfloor%7B%282n%29%5E%281%2F2%29%2B1%2F2%7D

Answer 7

As usual its a mix of both @INewton , im trying to solve these problems efficiently and i feel bored working all these on my own so.. you get the idea :)

Answer 8

i see floor function is a nice idea

Answer 9

@mathmath333 thats working !
http://www.wolframalpha.com/input/?i=Table%5Bfloor%28%282n%29%5E%281%2F2%29%2B1%2F2%29%2C+%7Bn%2C1%2C10%7D+%5D

how did you figure it out ? xD

Answer 10

lol googled it!

Answer 11

http://math.stackexchange.com/questions/455511/formula-for-the-nth-term-of-1-2-2-3-3-3-4-4-4-4-5

Answer 12

That link is roughly how I did it (I couldn't reply with a long post because the the 'post' button gets hidden below that weird chat box?) I'm still curious how to arrive at the simpler formula, though.

Answer 13

what about interpolating a function using Lagrange and combine it with floor function?

Answer 14

If you're comfortable with getting \[\Large \lfloor \frac{1+\sqrt{1+8n}}{2} \rfloor\] getting the simpler formula shown there not too far away: \[\Large \lfloor \frac{1}{2} + \sqrt{2n} \rfloor \] Just take the half inside the square root which becomes a fourth and notice for larger and larger n it becomes negligible and won't affect the result.

Answer 15

that looks neat! initial derivation using quadratic formula and floor function looks a bit tricky though... im still working on it..

Answer 16

Here's the derivation if you're interested:

Answer 17

Since n is a triangular number and k is counting up we really want to be able to put in the triangular number to get the term we want. So we have to invert this\[\Large n=\frac{k(k+1)}{2}\] \[\Large 2n = k^2+k = (k+\frac{1}{2})^2-\frac{1}{4} \\ \Large \frac{1}{4}+2n = (k+\frac{1}{2})^2 \\ \Large 1+8n = 2^2(k+\frac{1}{2})^2 \\ \Large \sqrt{1+8n} = 2k+1 \\ \Large \frac{-1+\sqrt{1+8n}}{2} = k \]So now we almost have it, except nobody likes minus signs so instead of writing it with a ceiling they use the floor \[\Large \lceil \frac{-1+\sqrt{1+8n}}{2} \rceil = \lfloor \frac{-1+\sqrt{1+8n}}{2} +1 \rfloor \\ \Large =\lfloor \frac{1+\sqrt{1+8n}}{2} \rfloor\]

Answer 18

Ahh nice so we need to eyeball
\[\large k-1\lt \frac{-1+\sqrt{1+8n}}{2} \le k\]

Answer 19

I don't think we are eyeballing that, it's just an identity (or at least should be) as long as x is not an integer (it is always irrational): \[\Large \lceil x \rceil = \lfloor x+1 \rfloor\]

Answer 20

\[ \lfloor{\frac{1 + \sqrt{8n+1}}{2}}\rfloor \not= \lfloor{ \frac{1}{2} + \sqrt{2n}}\rfloor \]
(e.g. for n = 3, LHS = 3 != 2 = RHS - the LHS is exactly 3 before the floor, and the RHS 2.94....)

It seems to be "off by one", so if we let n = n+1 in the RHS, they are the same (at least up to about 100 million. However, I am not convinced that the 1/4 "becomes negligible" for larger n - in fact, it seems to matter more for larger n. It probably is a valid formula, but I think a proof is required for the edge cases.

Answer 21

(i.e. I do not think it's obvious that it will not be the case that, for some very large n, the 1/4 matters enough so that the first/last terms in the sequence which take this n are pushed just over an integer value by the 1/4 we remove from the square root. I think it's true, but the proof - which would only bee needed for these cases - seems to require a bit of algebra. Which is a pain when you throw in floors.)

Answer 22

I don't think we are trying to use the function for small n, so the fact that it fails isn't really concerning and I think we can say something along these lines: \[\Large \lim_{n \to \infty} \sqrt{\frac{1}{4} +2n} \approx \sqrt{2n}\]

Answer 23

Maybe we can use a taylor series or something to look at the approximation

Answer 24

But for /every/ triangular number, the sqrt(8x + 1)... approximation will take an exact integer value, and the other will necessarily be lower (and hence round down to another integer).

Answer 25

The difference we are talking about is literally this \[\Large \sqrt{\frac{1}{4} +2n} - \sqrt{2n}\] Let's take the limit as n goes to infinity \[\Large \lim_{n \to \infty} \sqrt{\frac{1}{4} +2n} - \sqrt{2n} \\ \Large \lim_{n \to \infty} \sqrt{\frac{1}{4} +2n} - \sqrt{2n} *\frac{\sqrt{\frac{1}{4} +2n} +\sqrt{2n} }{\sqrt{\frac{1}{4} +2n} + \sqrt{2n} } \\ \Large \lim_{n \to \infty} \frac{1/4 }{\sqrt{\frac{1}{4} +2n} + \sqrt{2n} }=0\]

Answer 26

What value does this have to be to have a difference of 1 or greater, which is probably more what you're looking for? https://www.desmos.com/calculator/pjzqiig10f

Answer 27

Kai, my earlier question on eyeballing was about how we move from:
\[ \Large \frac{-1+\sqrt{1+8n}}{2} = k\]

to this line
\[\Large \lceil \frac{-1+\sqrt{1+8n}}{2} \rceil \]

last night i was having some troubles wid `ceil` function lol

Answer 28

I'll just recopy what I put, but it might be slightly off for only a couple special values like when n=1.

---

I don't think we are eyeballing that, it's just an identity (or at least should be) as long as x is not an integer (it is always irrational): \[\Large \lceil x \rceil = \lfloor x+1 \rfloor\]

Answer 29

I was stuck at one step before where we are writing the quadratic solution as `ceil` function...

I get moving from `ceil` to `floor` part...

Answer 30

http://gyazo.com/c4f621b61b8c4f299a84fcd9cf584d91

Answer 31

but im comfortable wid that now as it makes sense intuitively.. :)

Answer 32

Ohhh why is there even a ceiling or floor function at all is kind of your question?

Answer 33

yes exactly, my question was how did that `ceil` function came up all off sudden... but im at peace wid it now :)

Answer 34

Oh, I don't think I am completely comfortable with it either honestly lol.

Answer 35

I just did it, but I can't seem to see why it's exactly justified other than I saw that it came up with the same answer as them.

Answer 36

\[ \Large \frac{-1+\sqrt{1+8n}}{2} = k = a_n\]

this is only true when \(n\) is a triangular number

after this we're introducing `ceil` function and saying thats the general formula..

thats should be okay i guess as it becomes kinda obviou from the pattern in the sequence..

Answer 37

True, since when n=0 we have k=0 and n=1 we have k=1, but finally n=2 we have k approximately greater than 1 but not quite 2, so we are sorta forced to round up. It seems like it will always have to round up except for when it's at the number itself in which case rounding up to itself can't do any harm.

Answer 38

No, you misunderstand me. The second equation you 'simplified it' into by 'ignoring 1/4' gives a DIFFERENT sequence. To see this, consider its value for ANY triangular number, regardless of size. The first will give and exact integer result, and the version ignoring 4 will NECESSARILY give a lower value, and hence round down (with floor) to the integer below.

However, I proved that floor (sqrt(2n) + 1/2) is a valid approximation for the sequence shifted by 1. Limits are overkill, this is a simple algebra problem.

As sqrt(2n) + 1/2 is increasing, it is clear we only need consider the value when a) n is triangular and b) n-1 is triangular. These are the edge cases where the floor 'jumps' The first should give x, where n is the xth triangular number. The second should give x+1, when n-1 is the xth triangular number.

To prove these cases, we need to show the following inequalities can never happen:

a) sqrt(x(x+1)) + 1/2 > x+1
b) sqrt(x(x+1) + 1) + 1/2 < x+1

It's fairly easy to show that both are always false (and a good exercise).

Answer 39

My concern was not that the difference sqrt(2n + 1/4) - sqrt(2n) would go above 1. All that needed to happen was for them to be different enough that they were either side of an integer - in which case their floors would have a difference of 1 - so the absolute value of this difference is irrelevant.

Answer 40

Sorry, that second inequality should be sqrt(x(x+1) + *2*) + 1/2 < x+1. This comes from:

2 * (x(x+1)/2 + 1). Where x(x+1)/2 is the xth triangular number. The first inequality should also not be strict, but it doesn't matter in this case, as the stronger case holds.

Answer 41

@INewton You're definitely right, I was literally punching air explaining that haha. I guess this whole thing is really quite fuzzy to me, for some reason there's something peculiar about inverting the formula for triangular numbers and putting the rounding functions on it. They're fun functions to play with though.

Answer 42

Haha, yeah this is definitely an an interesting question. You gave a good explanation of how to get to the original quadratic solution, and good intuition for where the sqrt(2n)... came from, which I had no idea. Something about it just didn't seem /quite/ right though, so I wrote a program to simulate it and get a better idea of what was going on. Then finally I could put the proof together, without having to mess around with horrible floor functions.

By the way, if you're interested, http://en.wikipedia.org/wiki/Golomb_sequence is a similar sequence, but even crazier. I came across it in a problem once. Maybe one day I'll find a general term for that sequence ;-)

Answer 43

Woah I this is almost the same, but incredibly harder. Weird, how did you find this, does this relate to anything else or is it just sort of a random thing someone came up with? Also what programming language do you use?

Answer 44

It's the basis of a Project Euler problem ( https://projecteuler.net/problem=341 ), but I haven't solved it. This question reminded me of it :-) Like a lot of number theory - I think it's probably something that he came up with for fun, or to prove a sequence with whatever properties it has exists.

Looking into it, the guy who invented it seems to be involved in 'recreational mathematics' (the kind of stuff Jon Conway does, like the game of life) http://en.wikipedia.org/wiki/Recreational_mathematics

Java, normally. But I really need to learn C++.

Answer 45

Oh awesome, I do PE with Java as well, but I'm not very far into it only about 16 or so in over the past year. I first heard about Conway from knot theory since he has some quite fascinating things he plays with. Really sounds like he lives the dream job haha.