Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
The Lounge
Feedback and Announcements
Complete Induction -- How to remove my subscription to this very old thread?
Reply to thread
Message
[QUOTE="lovemake1, post: 4099142, member: 208992"] [h2]Homework Statement [/h2] Question asks to prove that all binary string that begins and ends with the same number(bit) has an even number of occurences of substrings from {0,1} Hint: you may find useful to combine claims about strings that start and end with different bit[h2]Homework Equations[/h2]{0} = {} since 0 is a multiple of 2 it holds. {11} = {} since 0 is a multiple of 2 it holds. eg 010010 = (01), (10), (01) (10) [h2]The Attempt at a Solution[/h2]My induction hypothesis was, for all natural number n, assume that p(j) holds for some integer j such that 0 <= j < n, that is a binary string with length j that begins and ends with the same bit has an even number of ooccurences of substrings from {0,1} so, let j = n - 1 and by I.H we know that p(j) holds. j, begins and ends with the same bit. and can be represented like so, P(j) = 2t for some integer multiple t. since 1st and last digit of j is the same, we know if n = jlast then there are no additional sets created so the equation will still be p(n) = 2t + 0; but if we were to add n != jlast, then there would be 1 extra subset at the end since ...01 or ...10 will take place. therefore, the equation will now be p(n) = 2t + 1; even number + odd = odd. hence we've shown that for all n, if first and last digit of string is the same, there are even number of substrings from {0,1} I feel like I have done too much explaining in english and not enough mathenatical proof. is there somewhere I went too far? help is appreciated. [/QUOTE]
Insert quotes…
Post reply
Forums
The Lounge
Feedback and Announcements
Complete Induction -- How to remove my subscription to this very old thread?
Back
Top