Discrete Math - Strong Induction Question

1 reply · 4K views · last reply
Rosebud
Messages
25
Reaction score
0

Homework Statement


Prove by Strong Mathematical Induction[/B]
Text problem: Define a sequence a1, a2, a3, ... with a1 = 1, a2 = 3, and ak = ak-1 + ak-2 for all integers k ≥ 3 (the Lucas sequence). Use strong mathematical induction to prove that an ≤ (7/4)^n for all integers n ≥ 1.


Homework Equations


N/A

The Attempt at a Solution


The steps to solving this problem are shown below. I understand all steps of the problem until the part where it says 44/49 becomes 49/49 since 44 < 49. Can someone please explain the logic behind that step? Thank you.
Step 1 of 2 from a strong induction proof: sequence a1=1, a2=3, ak=ak-1+ak-2 shown to satisfy an ≤ (7/4)^n, with basis checks for n=1 (1 ≤ 1 3/4) and n=2 (3 ≤ 49/16 = 3 1/8).
Step 1 of 2 from a strong induction proof: sequence a1=1, a2=3, ak=ak-1+ak-2 shown to satisfy an ≤ (7/4)^n, with basis checks for n=1 (1 ≤ 1 3/4) and n=2 (3 ≤ 49/16 = 3 1/8).
Handwritten-style typeset inductive step of a proof: assume a_n ≤ (7/4)^n for n = 1 to k, show a_{k+1} = a_k + a_{k-1} < (7/4)^k + (7/4)^{k-1}, factor out (7/4)^{k+1} to get (7/4)^{k+1}(4/7 + 4²/7²), equal to (7/4)^{k+1}·44/49, then less than (7/4)^{k+1}·49/49 since 44 < 49, which equals (7/4)^{k+1}.
 
Last edited:
If a>0 then a*(44/49) < a*(49/49).
Sort of like saying that f(x) = ax is strictly increasing.