Hogatt's Theorem

Prove Hogatt's Theorem: Any integer number can be written as a sum of terms of Fibonacci series. See attached file for full problem description.

Discrete Structures (Recursively Defined Sequences; Basis Definitions; Induction)

The attached sequences are "recursively defined" (for definition please see attachment). Please answer the questions regarding each sequence. Thank you.

Recursive Definition Sequence

The attached sequence of numbers is recursively defined. Please complete the sequence.

Induction Proof : Strings of Digits

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 tr ...continues

Induction Problem

Attached in word document Numbers of the form tn = n (n+1) / 2 are called triangular numbers, because marbles arranged in an equilateral triangle, n on a side, will total... (see attachment)

Error Correcting Code

If no two strings in a code differ in fewer than three positions, the we can actually correct a single error, by finding the unique string in the code that differs from the received string in only one position. It turns out that there is a code of 7-bit strings that corrects single errors and contains 16 strings. Find such a c ...continues

Recursive definition

We can define sorted lists of integers as follows: BASIS - A list consisting of a single integer is sorted. INDUCTION - If L is a sorted list in which the last element is a and if b >= a, then L followed by b is a sorted list. Prove that this recursive definition of "sorted list" is equivalent to our original, nonrecurs ...continues

Induction by Recursion : Even-Parity Strings

Define recursively the set of even-parity strings, by induction on the length of the string. Hint: It helps to define two concepts simultaneously, both the even-parity and odd-parity strings.

Discrete Math : Subsets and Elements

Let S = {1,2,3,4,5,6,7,8}. Determine: (a) The number of subsets of S (b) The number of subsets of S with at most four elements (c) The number of ordered lists with elements chosen form S (with possible repititions) (d) The number of ordered lists with nine elements chosen form S with no repititions (e) The number ...continues

Discrete

Let Pn be the product of the first n odd numbers... (see attachment)