Securing Higher Grades Costing Your Pocket? Book Your Assignment at The Lowest Price Now!

Get assignment help service to meet the high expectations of your professors


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 }
Assignment Help Features
Assignment Help Services
  • Assignment Help
  • Homework Help
  • Writing Help
  • Academic Writing Assistance
  • Editing Services
  • Plagiarism Checker Online
  • Proofreading
  • Research Writing Help
QR Code Assignment Help