Results 1 to 3 of 3

Math Help - Induction Proofs

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    Induction Proofs

    Problem 1: I need to use induction to prove that the number of binary strings of length n equals 2^n.

    Problem 2. Number of binary strings of length at most n equals 2^(n+1) -1

    Problem 3. for every integer n > 0 or n = 0 there are integers a and b such that 2a + 3b = n.


    Can somebody help me out on these 3 problems, they are my last posts as i finish my course tomorrow! It be great help if you guys can show me these 3 questions cause they will be in exam i bet!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kurac View Post

    Problem 3. for every integer n > 0 or n = 0 there are integers a and b such that 2a + 3b = n.
    they're all easy. i'll do 3) and i'm sure you'll get help for 1) and 2) before your exam!

    for n = 0 choose a = b = 0. assuming there are integers a, b such that 2a + 3b = n, we let c = a - 1 and d = b + 1. then 2c + 3d = 2a + 3b + 1 = n + 1, and our induction is complete.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,443
    Thanks
    1863
    For (1), if n= 1 the only binary strings of length 1 are "0" and "1" so there are 2= 2^1.

    Assume that for some k, the number of binary strings of length k is 2^k. From each of those, you can create a new string of length k+1 by appending either a "0" or a "1"- so you can create 2 new strings of length k+1 from each string of length k.

    For (2), The number of strings of length less than or equal to k+1 is the number of strings of length less than or equal to k plus the number of strings of length k+1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proofs by Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 11:11 AM
  2. Induction proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 09:32 PM
  3. proofs by induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 28th 2009, 06:29 AM
  4. A couple induction set proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 19th 2009, 02:09 AM
  5. proofs by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 25th 2007, 05:14 AM

Search Tags


/mathhelpforum @mathhelpforum