
Algebra PreAlgebra and Basic Algebra Math Forum 
 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. 
November 10th, 2012, 12:08 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,931 Thanks: 2205 
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. 
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? 
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.

November 10th, 2012, 04:16 PM  #5  
Global Moderator Joined: Dec 2006 Posts: 20,931 Thanks: 2205  Quote:
Quote:
 

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 