Results 1 to 4 of 4

Math Help - finding recurrence relation - question #2

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    finding recurrence relation - question #2

    Find a recurrence relation for an, n>=0 where an is the number of n-digit sequences (each digit taken from {0, 1, 2, . . . , 9}) that contain 666 somewhere in the sequence.
    Last edited by mr fantastic; November 26th 2009 at 03:00 AM. Reason: Changed post title
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,911
    Thanks
    775
    Hello, sbankica!

    Find a recurrence relation for a_n,\:n \geq 0,
    where a_n is the number of n-digit sequences
    (each digit taken from {0, 1, 2, ... 9})
    that contain 666 somewhere in the sequence.
    Consider a_7, the number of 7-digit numbers that contain "666".


    One of them is: . N \:=\:ab666cd

    Write it like this: . \_\:a\:\_\:b\:\_\:6\,6\,6\:\_\:c\:\_\:d\:\_

    There are 6 spaces ( n-1 spaces) in which to insert the eighth digit.
    . . and there are 10 choices for the eighth digit.

    Hence, there are: (10)(6) ways to change N into an 8-digit number.

    That is: . a_8 \;=\;(10)(6)a_7


    In general: . a_n \;=\;10(n-1)a_{n-1}



    Edit: I suspect that there is some duplication in my solution,
    . . . .but I'm unable to eliminate it.
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    The above solution is obviously wrong!
    This problem is very complicated!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Let b(n) be the number of n-digit sequence which contains no 666
    anywhere in the sequence.
    Obviously a(n)=10^{n}-b(n).
    Divide b(n) into two classes:
    Class A: s(n) be the number of sequence such that the n-th digit is not 6.
    Class B: t(n) be the number of sequence such that the n-th digit is 6.
    Then b(n)=s(n)+t(n),
    To find b(n+1), we need to find s(n+1) and t(n+1):
    It is very easy to (see)verify that, we have the following recursive definition:
    s(n+1)=9b(n);
    t(n+1)=s(n)+s(n-1);
    And
    s(1)=9,t(1)=1,b(1)=10;
    s(2)=90,t(2)=10,b(2)=100.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation question
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 3rd 2010, 08:17 PM
  2. find a recurrence relation question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 08:03 PM
  3. Finding a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 26th 2009, 07:41 AM
  4. Finding a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 02:39 PM
  5. Replies: 1
    Last Post: October 24th 2008, 11:27 AM

Search Tags


/mathhelpforum @mathhelpforum