My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 10th, 2012, 11:01 AM   #1
Newbie
 
Joined: Nov 2012

Posts: 25
Thanks: 0

Recurrence equations

Hi.

I am starting my adventure with recurrence relations and I've stumbled upon a few problems. Could you help me solve it? I know how to solve recurrence equations with only etc and scalars in it. I can also guess the formula, if it is easy enough, and them prove it by induction. But I these don't work here:

First some equations:

1)

2)

3)

4)

5)

6)

7)

And some problems:

1) Find the number of strings length n consisting of numbers 0,1,2 where the following bits differ at most 1. What I mean is that such strings should look like that: 00000000111111222222222111111100000001111110000000 01111100000111112222211111
I've tried to find a recurrence pattern (if we begin with 0, then after the 0s we can only put 1s, but after 1s there can be 0s or 2s, but then after 0s and 2s there can be only 1s and there we go again) but I have no idea how to write such a recurrence since there can be any number of 1s,2s 0s used.

2) similar, only this time we form bit strings using numbers 0, 1, 2, 3 and we need to find the number of strings in which 0 and 1 are not next to each other.

Please help.
wilhelm is offline  
 
November 10th, 2012, 12:08 PM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 20,467
Thanks: 2038

I'll make some suggestions initially.

1) Calculate a(3), a(4), etc, and a simple pattern will become obvious.

2) Use for which a simpler equation holds.

3) Use where p and q are chosen to produce a simpler recurrence relation.

Problems 4 - 7 are somewhat similar. Try to make progress with the first. If you succeed, it's likely that a similar approach will help with the rest.
skipjack is offline  
November 10th, 2012, 12:49 PM   #3
Newbie
 
Joined: Nov 2012

Posts: 25
Thanks: 0

Re: Recurrence equations

Thank you very much.

Is it possible that the second formula has square roots of 2 in it?
wilhelm is offline  
November 10th, 2012, 01:08 PM   #4
Newbie
 
Joined: Nov 2012

Posts: 25
Thanks: 0

Re: Recurrence equations

Could you give me a hint as to what to do when there is a in a recurrence equation? Setting doesn't work out right.
wilhelm is offline  
November 10th, 2012, 04:16 PM   #5
Global Moderator
 
Joined: Dec 2006

Posts: 20,467
Thanks: 2038

Quote:
Originally Posted by wilhelm
Is it possible that the second formula has square roots of 2 in it?
You would know if you'd calculated several more terms in the sequence or used the suggested substitution.

Quote:
Originally Posted by wilhelm
Could you give me a hint as to what to do when there is a in a recurrence equation?
It's advisable to solve the previous problem first, as it should make it easier to find a useful substitution for this problem.
skipjack is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
equations, recurrence



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Coupled Partial Recurrence Equations maxiim Applied Math 7 December 15th, 2011 09:13 AM
recurrence relation fn+4 fe phi fo Applied Math 3 December 4th, 2011 09:22 AM
recurrence CarpeNoctum Computer Science 3 October 12th, 2010 02:08 PM
Is there any one can help me with this recurrence ?? Student 100 Computer Science 2 November 25th, 2008 05:52 AM
gcd recurrence nithins Number Theory 1 April 15th, 2007 03:08 AM





Copyright © 2019 My Math Forum. All rights reserved.