Explore BrainMass

Explore BrainMass

    Induction Proof : Strings of Digits

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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?

    © BrainMass Inc. brainmass.com December 24, 2021, 5:03 pm ad1c9bdddf

    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, ...

    Solution Summary

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