Results 1 to 3 of 3
Like Tree3Thanks
  • 2 Post By romsek
  • 1 Post By Archie

Thread: recurrence equations

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    Hong Kong
    Posts
    15

    recurrence equations

    Hey, I need a little help:

    Solve this with recurrence equations: One string with decade digits is valid only if the string consists even number of zeros. How many valid words with length n are there?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,770
    Thanks
    2417

    Re: recurrence equations

    neat problem.

    Suppose you've got a $k$ digit string

    There are $v_k$ valid strings and $10^k-v_k$ invalid strings.

    We select the $k+1$th digit, $d_{k+1}$

    If $d_{k+1}=0$ then adding this to all the currently invalid strings makes them valid.

    Similarly if $d_{k+1}\neq 0$ then adding this to all the currently valid strings keeps them valid.

    so we have

    $v_{k+1} = 9 v_k + (10^k-v_k) = 8v_k + 10^k$

    there are $9$ valid strings of length $1$ so $v_1 = 9$

    and this completes the recursion equation.

    a bit of toying with this reveals

    $v_n = 9 \cdot 8^{n-1} + \displaystyle \sum_{k=2}^n 8^{n-k}\cdot 10^{k-1} =

    9\cdot 8^{n-1}-2^{n-3} \left(5\cdot 2^{2 n}-4\cdot 5^n\right)$
    Last edited by romsek; Apr 17th 2017 at 07:28 AM.
    Thanks from Archie and Breh
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: recurrence equations

    Decade digits are \{0,1,2,...,9\}?

    If you wish to find c(n) the count of words length n, you can consider how such words can be made from those of length (n-1) (you must add a non-zero digit) and from those of length (n-2) (by adding two zeros). You thus get an expression of the form

    c(n) = A c(n-1) + Bc(n-2)
    where A and B are either constants or expressions in n

    The trick is to avoid double counting. This is why from words of length (n-2) we only look at adding two zeros, because if we add two non-zeros, we pass through the (n-1) case on the way to words of length n.
    Thanks from Breh
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with a pair of recurrence equations.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 14th 2014, 04:18 AM
  2. Recurrence equations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 10th 2012, 11:39 PM
  3. Solving Recurrence Equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 20th 2012, 04:42 AM
  4. how to merge system of recurrence equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 28th 2011, 02:01 PM
  5. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM

/mathhelpforum @mathhelpforum