Results 1 to 3 of 3

Math Help - Proof by mathematical induction of a recursion equation

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    4

    Proof by mathematical induction of a recursion equation

    The recursion equation for the problem:

    A "codeword" from alphabet {0,1,2,3} is said to be "legitimate" if it contains an even number of zeros. Thus for instance, the codeword 31010 is legitimate whereas 01010 is not. How many n-letter codewords are legitimate ?

    is N(n) = 2^(2n-1) + 2^(n-1)

    Can some one help me with proving N(n) by mathematical induction ?

    I know that the first step is to show that N(1) is true.
    So if I plug in n=1 in the equation above the answer is three and it is true becasue legitimate codewords that are 1-letter long are {1},{2} and {3} and therefore there are three.

    I think the next step is to assume that N(n) is true and then to see whether or not N(n+1) is true by plugging in n+1 for n in the recursion equation above.


    Thanks in advance
    Last edited by thw002; September 28th 2009 at 07:08 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    You can't just put n+1 to it, you have to prove it It means count all such words for n+1.

    1. Prove for N(0):

    There are only 3 "legitimate" values and N(0) = 3. So it's true!

    2. Prove for N(n+1) if we know that it's true for N(n)

    Let's count how many "legitimate" words could be for N(n+1):
    a) We can construct "legitimate" word length n+1 by adding 1, 2 or 3 to "legitimate" word of length n, so there will be 3*N(n) such "legitimate" words;
    b) By adding 0 to a non "legitimate" word of length n. There will be (2^2n-N(n)) such "legitimate" words of length n;

    N(n+1) = 3N(n)+(2^{2n}-N(n)) = 2^{2(n+1)-1}+2^{(n+1)-1}

    So it's totally true
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello ialbrekht
    Quote Originally Posted by ialbrekht View Post
    You can't just put n+1 to it, you have to prove it It means count all such words for n+1.

    1. Prove for N(0):

    There are only 3 "legitimate" values and N(0) = 3. So it's true!

    2. Prove for N(n+1) if we know that it's true for N(n)

    Let's count how many "legitimate" words could be for N(n+1):
    a) We can construct "legitimate" word length n+1 by adding 1, 2 or 3 to "legitimate" word of length n, so there will be 3*N(n) such "legitimate" words;
    b) By adding 0 to a non "legitimate" word of length n. There will be (2^2n-N(n)) such "legitimate" words of length n;

    N(n+1) = 3N(n)+(2^{2n}-N(n)) = 2^{2(n+1)-1}+2^{(n+1)-1}

    So it's totally true
    I like the simplicity of your argument, but I don't quite understand it. Can you clear up some questions for me?

    • In (a) when we construct a legitimate word of length n+1 from a word of length n, where does the extra 1, 2 or 3 get added?


    • In (b), where does the extra zero get added to the non-legitimate word?


    • How can you be sure that none of the new words formed by method (a) aren't the same as some of the words formed by method (b)?


    Grandad

    PS Ah - I have it. It really is simple, isn't it? Every legitimate word of length n+1 either ends in (i) a zero or (ii) a non-zero. If we remove the last digit, then, we get a word of length n which is either (i) non-legitmate, or (ii) legitimate, respectively.
    Last edited by Grandad; September 29th 2009 at 10:46 PM. Reason: Add PS
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 24th 2011, 03:33 PM
  2. Proof by mathematical Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 2nd 2011, 08:26 AM
  3. Proof using mathematical induction
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 22nd 2010, 02:36 AM
  4. Mathematical induction proof, help?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 23rd 2010, 08:39 PM
  5. mathematical induction recursion
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 27th 2007, 08:18 AM

Search Tags


/mathhelpforum @mathhelpforum