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

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.