Math Is Fun Forum

goldman-russell

Guest

Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

This is not a homework question, but something I was wondering about solving difference equations.

For example, how would I solve the following difference equation;

Since it has homogeneous and inhomogeneous parts together (and two unknowns - n and p) I don't know what to do. Any help on how I would solve this would be appreciated, thanks.

(For where I got this formula from - I found this when thinking about a formula that would give me the minimum number of moves to complete a game of Tower of Hanoi with n discs and p poles.)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi goldman-russell;

I would try to get the p out of the indices, either by coming up with another difference equation. Or by having 2 coupled difference equations.

You say that you are modelling a tower of hanoi problem. If you have the data that for n's and p's, provide it and I will find new difference formulas for it. This is the simplest way.

Also you might want to look here:

http://mathworld.wolfram.com/TowerofHanoi.html

From my general knowledge of it the Tower of Hanoi with arbitrary pegs might be an open problem or at least a very difficult one.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

Sorry, I left out the co-efficient 2. It should read;

I'm not sure I completely understand what to do; is this working correct?

Let

for

.

Where do I go from here? I think I have to put the first root in like so;

But what do I put in the "B" bracket? Where does the 'm' come from, and what does it do/why is it there?

As for the data I collected, here it is:

For 3 poles, we know that the rule is 2[sup]n[/sup] - 1. This is clear because we have 1 move for 1 disc, 3 moves for 2 discs, 7 moves for 3 discs, and 15 moves for 4 discs, and so on.

I tried this with 4 poles and I found that:

Format: Discs | Moves

1 | 1
2 | 3
3 | 5
4 | 9
5 | 13

So the recurrence relation is F[sub]n[/sub] = 2F[sub]n-3[/sub] + 7

I did the same thing for 5 poles but I no longer have the results. But I did write down the recurrence relations for 3 poles, 4 poles and 5 poles.

3 poles: F[sub]n[/sub] = 2F[sub]n-1[/sub] + 1
4 poles: F[sub]n[/sub] = 2F[sub]n-3[/sub] + 7
5 poles: F[sub]n[/sub] = 2F[sub]n-5[/sub] + 13

So in general:

P poles: F[sub]n[/sub] = 2F[sub]n - 2p + 5[/sub] + 6p - 17

Where p is the number of poles.

So I want to find a formula connecting poles, discs, and number of moves... and I think I can do this by solving this difference equation.

Thanks for your help. I'd like to try and do as much of this 'challenge' as I can myself, though... a friend set this puzzle for me as I was playing this game so I feel it would be wrong if I had someone else do it for me!

But I certainly need help solving the difference equation.

Thanks!

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

So the recurrence relation is F[sub]n[/sub] = 2F[sub]n-3[/sun] + 7

Sorry, this should read: F[sub]n[/sub] = 2F[sub]n-3[/sub] + 7

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

It came out badly again... it should say F[sub]n[/sub] = 2F[sub]n-3[/sub] + 7. Sorry for this inconvenience.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi;

No inconveniece at all. Don't worry about it.

First we can start here:

This is the sequence for 4 pegs:

1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, 193, 225, 257, 289, 321, 385, 449, 513, 577, 641, 705, 769, 897, 1025, 1153, 1281, 1409, 1537, 1665, 1793, 2049, 2305, 2561, 2817, 3073, 3329, 3585, 3841, 4097, 4609, 5121, 5633...

Your recurrence, Fn = 2Fn-3 + 7 works up to 41 where 2 * 17 + 7 = 41 but notice for the next one 49 ≠ 2* 25 + 7

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

darn! I've wasted a lot of time trying to solve that difference equation. Oh well... so, according to that link you gave, the formula for a 4-pegged Tower of Hanoi with n discs is;

So now we just need to investigate a 5-pegged tower and a p-pegged tower...

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi goldman-russell;

Absolutely not, look at that formula. It contains an unknown variable called x. No one really knows what that is. No one really knows what is the optimum to move the disks in the 4 peg problem. That sequence that you generated and he generated may not be optimal. No one knows. You are in no man's land here. Unknown territory.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

So, what is stopping us from trying to find a formula for 4, 5, 6, 7 or p pegs? If your sequence was generated brute-force from a computer then I am more inclined to believe that sequence for 4 pegs is optimal - so I think we could come up with a general nth term for it. Should I try to find a formula for 4, 5, 6, 7 or p pegs or is it impossible?

Also: Where did you get that sequence? Do you think you could find a sequence of digits for 5 pegs, or perhaps more pegs? It would make it easier to generalise!

Thanks,
goldman-russell

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

That sequence was generated by the Frame - Stewart algorithm and has not been verified as being the shortest number of moves. A computer generated is not necessarily the best answer, especially when it is using an inefficient algorithm.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

But surely you can just  use a brute-force method and check every possible winning combination and see which one is the most efficient? How could I find a formula for 4, 5, 6, or p pegs?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi goldman-russell;

1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, 193, 225, 257, 289, 321, 385, 449, 513, 577, 641, 705, 769, 897, 1025, 1153, 1281, 1409, 1537, 1665, 1793, 2049, 2305, 2561, 2817, 3073, 3329, 3585, 3841, 4097, 4609, 5121, 5633...

This sequence has been verified as optimal up to 30 disks. The problem is no one knows what simple recurrence fits those numbers, or whether there even is one.

How could I find a formula for 4, 5, 6, or p pegs?

Since none is known for 4 pegs, I can't even suggest an idea for 5 or more. This I believe is an unsolved problem! For p pegs there may not be a simple relationship that exists.

Here is a quote from here that describes the problem.

http://www.experiencefestival.com/tower … and_beyond

Although the three-peg version has a simple recursive solution, the optimal solution for the Tower of Hanoi problem with four or more pegs is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints. Though it is not known exactly how many moves must be made, there are some asymptotic results. There is also a "presumed-optimal solution" that can be recursively applied to find a solution - see Paul Stockmeyer's survey paper for an ...

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

I can sort of see a pattern but not a recurrence relation... if we look at how we can progressively get from term to term, it looks like this:

2¹ + 2¹ + 2² + 2² + 2² + 2³ + 2³ + 2³ + 2³...

So whenever you end up with a difference of 2[sup]n[/sub], you add that difference to any term n+1 times.

But generating a recurrence relation is more difficult...

Can you see a pattern?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi goldman-russell;

I can sort of see a pattern but not a recurrence relation... if we look at how we can progressively get from term to term, it looks like this:

2¹ + 2¹ + 2² + 2² + 2² + 2³ + 2³ + 2³ + 2³...

Yes I noticed that too but how do we know that continues? Since we don't have a recurrence relation, sooner or later even with the fastest computers we are going to be unable to find the number of moves for n disks. Where do we go from there?

Please read this, specifically the part titled 4 pegs and beyond.

http://en.wikipedia.org/wiki/Tower_of_Hanoi

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goldman-russell

Guest

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi:

I hope it is possible. Have you noticed anything else about the sequence of numbers? I've been trying out different equations which have been generating some of the terms in this sequence but long strings of primes, too.

I hope there is a solution!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Solving Difference Equations with Homogeneous and Inhomogeneous Parts

Hi goldman-russell;

I hope there is a solution!

There may be. Keep this in mind that table for 4 pegs in post#12 has only been proven optimal for 30 disks, that table goes to 48 disks. I have seen tables up to 1000 disks and 4 pegs. Since we do not know whether the numbers past 30 are optimal, working on this seems counter productive. We have a small amount of data for 4 pegs and I could find nothing for 5 pegs.

I've been trying out different equations which have been generating some of the terms in this sequence

We can possibly find expressions that will fit the data, the trouble is we will not be able to prove them by induction.

I understand your wanting to continue to work on this problem. I have 5 or 6 problems myself that I probably will not solve in my lifetime, but I can't seem to stop working on them. If you are deriving pleasure out of this by all means continue, but please do not think you or anyone will solve it. So prepare yourself. Work on it because you love math but the solution will probably remain elusive,

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.