My Math Forum Recurrence equations

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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 $a_{n-1}, a_{n-2}$ 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) $a_{n}= \frac{ a_{n-1} ^{3} }{ a_{n-2} ^{2} }$ $|||a_1=1, a_2=2$ 2)$a_n=2 \frac{n-1}{n}a_{n-1}+ \frac{1}{n}||| a_1=1$ 3)$a_n=5a_{n-1}-6a_{n-2}+4n-3$ $|||a_1=1, a_2=2$ 4)$a_n=5a_{n-1}-6a_{n-2}+3^n$$|||a_1=1, a_2=2$ 5)$a_n=5a_{n-1}-6a_{n-2}+n3^n$$|||a_1=1, a_2=2$ 6)$a_n=5a_{n-1}-6a_{n-2}+n^2 2^n$$|||a_1=1, a_2=2$ 7)$a_n=5a_{n-1}-6a_{n-2}+(n^2+1)3^n$ $|||a_1=1, a_2=2$ 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,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 $^{b_n\,=\,na_n,}$ for which a simpler equation holds. 3) Use $^{b_n\,=\,a_n\,+\,pn\,+\,q,}$ 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 $3^n$ in a recurrence equation? Setting $b_n=a_n=pn=q-3^n$ doesn't work out right.
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 $3^n$ 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.

 Tags equations, recurrence

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post maxiim Applied Math 7 December 15th, 2011 09:13 AM fe phi fo Applied Math 3 December 4th, 2011 09:22 AM CarpeNoctum Computer Science 3 October 12th, 2010 02:08 PM Student 100 Computer Science 2 November 25th, 2008 05:52 AM nithins Number Theory 1 April 15th, 2007 03:08 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top