logo
+1-617-874-1011 (US)
+61-7-5641-0117 (AU)
+44-117-230-1145 (UK)
Live Chat

Induction Problems Assignment

Please answer the following induction problems.

  • Use induction to solve the following problem.

P: An integer of the form 7N-1 is divisible by 6 for all positive integers N

  • Use induction to solve the following problem.

P: A set which contains N elements has exactly 2N subsets.

  • Use induction to prove that a tree with N levels has at most 2N – 1 nodes. Note that the base cases are 1-levels ( meaning at most one node – the root), and 2-level has at most 3 nodes.
  • What exactly is wrong with the following strong induction “proof” that all horses in a field must be of the same color.

Induction on the number of horses in a field.

Base case : P(1) : Trivially, if a field has one horse in it then all horses in the field are of the same color.

Inductive Hypothesis P(k) : ASSUME that all horses in a field of K horses are the same color.

Show P(k+1) : Show that in a field with k+1 horses, all horses are the same color.

Remove a horse X from the field leaving k horses. By applying the inductive hypothesis to the remaining k horses we know that the remaining horses are all the same color.

Next, remove a DIFFERENT horse Y from the field. Again, by the inductive hypothesis, since there are k horses remaining then all of the horses in the field are the same color. Thus, since X != Y we can deduce that all k+1 horses are the same color.

Languages Quiz:

Draw the transition diagram (the graph) for a DFA accepting the following languages over the alphabet {`0,1`}.

{`
  1. L = {w | the 4th symbol from the end of w is a 1}
  1. L = {w | the # of 0’s in w is divisible by 3 and the # of 1’s is divisible by 2} Hint (look at remainders when divided by 3 for # of 0’s or by 2 for # of 1’s)
  1. L = { w | w is a string of 0’s and 1’s and when interpreted as a binary number (interpretted as base-10) w is an even number}
  1. L = { w | w begins with the substring 0010 or the substring 0110 }
  1. L = {w | w does not end with 0001 }
`}
Improve Your Grades with Custom Writing Help
Homework Help
Writing Help
Editing Services
Plagiarism check
Proofreading services
Research Project help
Custom writing services
scanner
E learning blogs

Disclaimer : The study tools and academic assistance/guidance through online tutoring sessions provided by AssignmentHelp.Net is to help and enable students to compete academically. The website does not provide ghostwriting services and has ZERO TOLERANCE towards misuse of the services. In case any user is found misusing our services, the user's account will be immediately terminated.