Okay, here's one for people who are "math guys":

I have a sequence such that

x_1 = 1

and

x_{n+1} = (1 + sum_i=1^n{{x_i}^2}) / n

for n>=1.

So the sequence begins 1, 2, 3, 5, 8, ...

Hypothesis: all x_n are integers.

Puzzle: prove or disprove the hypothesis.

This one has been bugging me on and off for over 10 years, so if someone has a solution, I'll be happy all day.

I think that should be 1,2,3,5,10 right? Just want to make sure i parsed that ascii formula right before i keep going

Yep. Every inch does have to be walked. But with John's method, part of the time they're walking at the same time in different areas, thus walking those inches twice as fast.

Yes.

A very succinct explanation. Well done!

tanstaafl.

so if your sequence is correct, then I think you mean "/ x_n" rather than "/ n". If you mean "/ n" then I think the sequence is 10 not 8, and after about n = 8 or so the numbers just explode upwards -- so much so that I can't even check to see if they really are integers (i wanted to run a few rounds to make sure the hypothesis was right).

However, if you meant "/ x_n" then that's a whole different ballgame... And those provably are integers, and it's actually the fibonacci sequence ... here's why:

define sum(a(b), b, c, d) to be "the sum of a(b) where b goes from c to d" .. to make parsing easier.

i'm switching to definiing n in terms of n-1 rahter than n+1 in terms of n... it made my brain hurt the other way for some reason.

restatement:
x_n = ( 1 + sum( (x_i)^2, i, 1, n-1) ) / x_(n-1)

pull out the last value of the sum:
x_n = ( 1 + sum( (x_i)^2, i, 1, n - 2) + (x_(n-1))^2 ) / x_(n-1)

divide through:
x_n = x_(n-1) + (1 + sum( (x_i)^2, i, 1, n - 2)) / x_(n-1)

the 1 + sum(.., n - 2) by definition is actually x_(n-1)*x_(n-2), which makes it now:

x_n = x_(n-1) + (x_(n-1)*x_(n-2)) / x_(n-1)

simplify and you get:

x_n = x_(n-1) + x_(n-2)

Like I mentioned, though, if you meant "/ n", then I need to go back to the drawing board.

Mike

I hate you for doing this to me ... So I got the "/ n" version down to:

x_n = [ (x_(n-1)) / (n - 1) ] * [ x_(n-1) + n - 2)

if you set x_1=1 and x_2=2 (wonder why it doesn't give you x_2 itself ... weird)

But now I'm kind of stuck ... If (x_(n-1))^2 + (n-2)(x_(n-1)^) somehow can be factored so that there is an (n-1) term in the numerator, that would cancel out the n-1 in the denominator and prove it to be true. But my brain has stopped functioning now that it is 2:30.

You realize you've set jEmplode back an entire day with this question

Mike

If you continue to use algebra on the BBS, I will have to hunt you down and kill you. Slowly. With a very dull knife.

In reply to:

---

If you mean "/ n" then I think the sequence is 10 not 8, and after about n = 8 or so the numbers just explode upwards -- so much so that I can't even check to see if they really are integers

---

Yes, I do really mean "/n", and yes, the numbers do get very big very quickly - it doesn't take long to run out of screen space And sorry for the mistake in my mental arithmetic - x_5 is indeed 10.

It's a long time since I've actually looked at this one, but ISTR making some progress by extending the sequence to include x_0 = 1. Then the expression becomes

x_{n+1} = sum_i=0^n{{x_i}^2} / n

and

n.x_{n+1} = (n-1)x_n + {x_n}^2

n (x_{n+1} - x_n} = {x_n}^2 - x_n
= x_n (x_n - 1)

So

x_{n+1} = x_n + x_n(x_n - 1) / n

Which would be great if I could somehow show that x_n or x_n - 1 is a multiple of n ... Unfortunately, it appears to alternate, so that for odd n, x_n is a multiple of n, and for even n, x_n - 1 is a multiple of n.

(Hmm, I'd forgotten how ugly TeX notation can be when you're not used to it)

Try a runsable spoon. not as sharp but quite effective.

x_{n+1} = x_n + x_n(x_n - 1) / n

I think you have to define x_2 explicitly .. My brain can't comprehend why, but if you use this to find x_2, it returns 1 -- mine did this too (since x_n - 1 = 0 for x_1) ... no idea why.

I wonder since we have two different equations, is it possible to set them equal to eachother and find out anything more interesting.

ms

"Why a spoon, cousin? Why not an axe?"

"Cause it's dull, you twit, it'll hurt more!"

Actually John never says that the other guy is walking. Maybe the other guy would hitchhike. Its would be faster. Maybe the other guy has a skateboard, a pod racer, a teleportation booth?

In reply to:

---

I think you have to define x_2 explicitly .. My brain can't comprehend why,

---

Yeah, I don't understand it either, as the original equation defines x_2 correctly. Perhaps there's a hidden divide-by-zero in the derivation (a bit like the one in the standard "proof" that 1=2).

Anyway, back to my DSSSL hacking - I've almost got something that interprets a user tag "print" to decide whether or not to output each subtree.

In reply to:

---

Try a runsable spoon. not as sharp but quite effective.

---

runcible?

I was thinking you could maybe get a little further because you know x_n was an integer and you could define:

since x_n was an integer, x_n = y / (n - 1) where y is an integer (1 + sum...). I haven't tried it yet, but I wonder if you sub that in to the x_{n+1}, does it get you any further (does that (n-1) cancel anything out). The next step has got to be that you take advantage of the fact that you know the previous number was an integer ........

ms

If you assume:
1. John and Fred walk the same speed
2. John and Fred ride the same speed
3. Lamposts are evenly spaced
4. Each section of travel is bounded by start point, town, or a lamp post.
5. There is a lamp post at the start and stop points, or the distance from the start or stop point to the nearest lamp post is the same as from lamp post to lamp post.
6. DELTA=(section walk time)-(section ride time)
7. They Ride faster than they walk.

John is correct.

For an even number of sections John and Fred will both arrive at town sooner (and at the same time). For each pair of sections, they will reduce there travel time by DELTA.

If the number of sections is odd, the scenario is the same as above except that John will arrive at town first and shave an additional DELTA off of his travel time (Fred gets no additional travel time reduction).

Since John concocted the proposition, perhaps he does not intend to chain up the bike to the first lamp post at all...

Since John concocted the proposition, perhaps he does not intend to chain up the bike to the first lamp post at all...

ROFL, best comment made so far.

"Since John concocted the proposition, perhaps he does not intend to chain up the bike to the first lamp post at all... "

damn, you made me crack me up

I have the proof, but it is too large to be contained within this box...

If you continue to use algebra on the BBS, I will have to hunt you down and kill you. Slowly. With a very dull knife.

So MathML in posts is enabled only for moderators?

Peter

Sorry runcible spoon. I'm sure that's the spelling I had before.

So it's a spork, right?? Oh, it has a cutting edge....

A knorkoon?

You are correct. I woke up at 1:30 in the morning going "wait... that isn't right!" I was just too lazy to post and point out my error. Oh well... It was caught.

Oh wait... you weren't talking to me.. I was refering to my equasion earlier on the walking thingie... the 2 on the bottom is incorrect, it should be 2X. Since all the trials I had tried were using 1 mph as x, it always worked, but it would NOT have worked if the speeds were 2mph and 5mph, respectively. anyway, blech.

Sorry runcible spoon.

Ah, nifty. In your first post, I thought you'd just horribly butchered the spelling of re-usable.

I guess that answers the Chunky Cambells Soup question...

A bump to this very old thread. Seems Click and Clack liked Doug's little puzzler.

Reading of question:
http://play.rbn.com/?url=cartalk/cartalk/demand/CT0417-07.ra

Reading of answer:
http://play.rbn.com/?url=cartalk/cartalk/demand/CT0418-04.ra

I don't know how long these links will last, they might take them down after a week or so.

Congrats, Doug! Do you get anything, like a mug or a Shameless Commerce gift certificate?

Ah, this brings back memories.

Do you get anything, like a mug or a Shameless Commerce gift certificate?

Naaah... they only give that stuff to the people who get the correct answer to the puzzler.

tanstaafl.