#### Question Details

Brief item decscription

Step-by-step solution file

Item details:

More:

CSC236 Fall 2016

Assignment #1: induction

due October 7th, 10 p.m. The aim of this assignment is to give you some practice with various forms of induction. For each question

below you will present a proof by induction. For full marks you will need to make it clear to the reader that

the base case(s) is/are veri ed, that the inductive step follows for each element of the domain (typically the

natural numbers), where the inductive hypothesis is used and that it is used in a valid case.

Your assignment must be typed to produce a PDF document (hand-written submissions are not acceptable). You may work on the assignment in groups of 1, 2, or 3, and submit a single assignment for the entire

group on MarkUs

1. Consider the Fibonacci-esque function g : 8

&gt;

&lt;1;

g (n) = 3;

&gt;

:g(n 2) + g (n if n = 0

if n = 1

1) if n &gt; 1 Use complete induction to prove that if n is a natural number greater than 1, then 2n=2  g (n)  2n .

You may not derive or use a closed-form for g (n) in your proof.

2. Suppose B is a set of binary strings of length n, where n is positive (greater than 0), and no two

strings in B di er in fewer than 2 positions. Use simple induction to prove that B has no more than

2n 1 elements.

3. De ne T as the smallest set of strings such that:

(a) &quot;b&quot; 2 T

(b) If t1 ; t2 2 T , then t1 + &quot;ene&quot; + t2 2 T , where the + operator is string concatenation.

Use structural induction to prove that if t 2 T has n &quot;b&quot; characters, then t has 2n 2 &quot;e&quot; characters. p 4. On page 79 of the Course Notes the quantity  = (1 + 5)=2 is shown to be closely related to the

Fibonacci function. You may assume that 1:61803 &lt;  &lt; 1:61804. Complete the steps below to show

that  is irrational.

(a) Show that ( 1) = 1.

(b) Rewrite the equation in the previous step so that you have  on the left-hand side, and on the

right-hand side a fraction whose numerator and denominator are expressions that may only have

integers, + or , and . There are two di erent fractions, corresponding to the two di erent factors in the original equation's left-hand side. Keep both fractions around for future consideration. 1 (c) Assume, for a moment, that there are natural numbers m and n such that  = n=m. Re-write the

right-hand side of both equations in the previous step so that you end up with fractions whose

numerators and denominators are expressions that may only have integers, + or , m and n.

(d) Use your assumption from the previous part to construct a non-empty subset of the natural

numbers that contains m. Use the Principle of Well-Ordering, plus one of the two expressions for

from the previous step to derive a contradiction.

(e) Combine your assumption and contradiction from the previous step into a proof that  cannot

be the ratio of two natural numbers. Extend this to a proof that  is irrational.

5. Consider the function f , where 3  2 = 1 (integer division, like 3==2 in Python): ( f (n) = 1

if n = 0

2

f (n  3) + 3f (n  3) if n &gt; 0 Use complete induction to prove that for every natural number n greater than 2, f (n) is a multiple of

7. NB: Think carefully about which natural numbers you are justi ed in using the inductive hypothesis

for. 2

STATUS
QUALITY
Approved

This question was answered on: Feb 21, 2020

Solution~00066437631.zip (18.37 KB)