Purchase Solution

Induction Proof : Strings of Digits

Not what you're looking for?

Ask Custom Question

If n >= 1, the number of strings using the digits 0,1, and 2 with no two consecutive places holding the same digit, is 3x2^n-1. For example, there are 12 such strings of length three: 010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, and 212.

Prove this claim by induction on the length of the strings. Is the formula true for n=0?

Purchase this Solution
Solution Summary

An induction proof for strings of digits is provided. The solution is complete.

Solution Preview

Proof:
We know, for n=3, the formula 3*2^(n-1) is correct. Now we suppose the formula is correct for n=k. When n=k+1, a string has the form
"ab&...&", where "b&...&" is a string of n digits. From the assumption, ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Probability Quiz

Some questions on probability

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

View More Free Quizzes
Related BrainMass Solutions

  • Grammar Induction

    (Answer.pdf) This is a proof regarding grammar and strings.

  • n-Bit Binary Strings with Fixed Digits

    9826 N-Bit Binary Strings with Fixed Digits I need to show that the number of n-bit binary strings that contain exactly two occurrences of 10 is C(n+1, 5).

  • Bit Strings

    So the total number of bit strings of length 6 is 2^6 = 64 (b) The second to the fourth digits can be filled in 2 ways, by either a zero or a one.

  • Counting methods

    84170 Counting 1. how many license plates can be made using three letters followed by the three digits or four letters followed by two digits 2. how many bit strings of length 10 contain either 5 consecutive 0s or five consecutive 1s.

  • Relations and Graph Theory.

    Solution: Number of base 10 numbers of 3 digits = 9*10*10 = 900 Number of three-digits numbers have no two consecutive digits equal = 9*9*9 = 729 Number of three digits numbers with at least one pair of consecutive digits equal = 900-729 = 171

  • Mathematical induction proof

    A complete, detailed proof (by mathematical induction) of the given assertion is presented, the importance of the basis step in an induction proof is discussed, and an example of how wrong results can be obtained if the basis step in an induction proof

  • Discrete Math : Logic (40 MC Problems)

    None of the above. 26. The proof of the correctness of a program is called: a. verification. b. induction. c. inference. d. validation. 27.

  • Cauchy integral formula proof

    26711 Partial Induction Proof of Cauchy's Integral Formula See attached file...it is a full induction proof of Cauchy Integral Formula, with the base case step missing.

  • use math induction for proof

    473509 Using Math Induction for Proof Find a formula for (1/(1*2) + 1/(2*3) + ..... + 1/ (n*(n+1) ) by examining the values of this expression for small values of n.

View More Related Solutions