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
the induction proof paradigm sheet.
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.
