The sequence is defined as dn=1 if n=0, ndn−1 otherwise. The goal is to prove ∀n∈Z+,d2n−1≤√2n−1 using induction. I successfully proved the base case, and laid out the induction step: assume d2k−1≤√2k−1 prove d2k+1≤√2k+1 But I am now struggling to algebraically prove the later inequality. I expressed d2k+1 in terms of d2k−1:
d2k+1=(2k+1)d2k−12k But I do not see any steps I can take from here. Any help is appreciated! I am new to this resource, please let me know if I formatted anything incorrectly!
Answer
Starting from
d2k−1≤√2k−1
multiply both sides with 2k+1 and you will get
2k⋅d2k+1=(2k+1)d2k−1≤(2k+1)√2k−1
Divide both sides by 2k:
d2k+1≤√2k+1√(2k−1)(2k+1)2k≤√2k+1√4k2−14k2≤√2k+1
No comments:
Post a Comment