Search for question
Question

# Problem 1

Inspired by Fibonacci, let us define a new series of numbers which we'll call the Conway numbers:

fi=1

f2 = 3

fn fn-1 + fn-2, for n 23.

Thus we have the sequence 1, 3, 4, 7, 11, 18, 29,...

-1

Prove by mathematical induction that for all n ≥ 1, fi= fa+2-3 by induction on n.

Hint: Using ellipses, this is equivalent to proving that

S₁+12+ + Sn=fn+2-3.

Hint: For full marks, use the 7-step process from lecture, tutorial, problem sets, and described on

Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution

details, the following is a general idea of how points are distributed for this problem. We give

partial credit where we can.

(12) Correctness. If your proof is not correct, this is where you'll get docked. You'll need to

(1) define P(n) that is a boolean function,

(1) ensure that P(n) is a function of n,

(1) use the correct n for the base case,

(1) correctly show that the base case is true,

(1) clearly state the induction hypothesis in terms of k (or some variable of your choice),

(6) prove the inductive step

(1) start with LHS of P(k+1) and manipulate to RHS (or vice-versa!). Do not start

with LHS RHS

(1) find a way to get the LHS of P(k) in your algebra somewhere, so that you can

(1) correctly apply the induction hypotheses

(1) clearly label where the IH is used.

(2) find a way to get the RHS of P(k+1) in your algebra somewhere.

(1) have a one-sentence conclusion that puts it all together (that we do at the end of every

induction proof.)

Note that if you followed the 7 steps then all but the inductive step were hopefully fairly

straightforward.

(2) Communication. We need to see a mix of notation and intuition. This proof is complex

enough that the "column format" is highly recommended, but a series of individual algebraic

equations separated by explanatory text is fine, too. A paragraph would be impossible to

understand. To get these points you must have sufficient detail to convince the reader of the

result, and not so many words that things get convoluted and confusing. If you skip too many

steps at once, or we cannot follow your proof, or if your solution is overly wordy or confusing,

this is where you'll get docked.