Loading DocumentEx3.1Q7
Q. Suppose that a∈R. Prove that if a3>a then a5>a.
Soln.
a3>a => a3−a>0
a5−a=a(a4−1)=a(a2−1)(a2+1)
a5−a=(a3−a)(a2+1)>0
a5−a>0 => a5>a.
Ex3.1 Q10
Q. Suppose x∈R and x=0. Prove that if x2+6(3√x+5)=x1 then x=8.
Soln.
To prove P→Q, use contrapositive ¬Q→¬P
Substitute x=8 in given eq
LHS = 82+6(3√8+5) = 64+6(2+5) = 707 = 101
RHS = 81
LHS = RHS
Proved ¬Q→¬P. So P→Q.
Hence proved.
Ex3.2 Q8
Q. Suppose that a and b are nonzero real numbers. Prove that if a<a1<b<b1 then a<−1.
Soln.
Given:
a<b (eq1)
a1<b1 (eq2)
a<a1 (eq3)
If a,b>0 or a,b<0, then a×b>0
Multiplying eq2 with a×b
a(a×b)<b(a×b) => b<a (Contradicts eq1)
So either a>0>b or b>0>a
If a>0>b, then a>b (Contradicts eq1)
So b>0>a (eq4)
Multiplying eq3 by a
a2>1 => a>1 or a<−1
If a>1, then a>0 (Contradicts eq4)
So a<−1.
Ex6.1 Q9b
Q. Prove that ∀n∈N, 6∣n3−n.
Soln.
For a number to be divisible by 6, it must be divisible by 2 and 3. (eq1)
Let L = n3−n = n(n2−1)= n(n+1)(n−1)
Either n or n+1 must be divisible by 2.
So L is divisible by 2. (eq2)
n−1,n,n+1 are consecutive 3 numbers.
So one of them must be divisible by 3.
So L is divisible by 3. (eq3)
So L is divisible by 6. (from eq1,eq2,eq3)
Ex6.1 Q10
Q. Prove that ∀n∈N, 64∣9n−8n−1.
Soln.
Proving by induction,
Base case:
For n=1, 91−8(1)−1=0
So divisible by 64.
For proving induction step assume 9n−8n−1=64×k such that k∈N.
Let L = 9(n+1)−8(n+1)−1
L = 9(9n)−8n−9
L = 9(9n)−72n+64n−9
L = 9(9n−8n−1)+64n
L = 9(64×k)+64n
So L is divisible by 64.
Hence proved by induction.
Ex6.1 Q11
Q. Prove that ∀n∈N, 9∣4n+6n−1.
Soln.
Proving by induction,
Base case:
For n=1, 41+6(1)−1=9
So divisible by 9.
For proving induction step assume 4n+6n−1=9×k such that k∈N.
Let L = 4(n+1)+6(n+1)−1
L = 4(4n)+6n+5
L = 4(4n)+24n−18n−4+9
L = 4(4n+6n−1)−18n+9
L = 4(9×k)−9(2n)−9
So L is divisible by 9.
Hence proved by induction.
Ex6.1 Q12
Q. Prove that for all integers a and b and ∀n∈N, a−b∣an−bn.
Soln.
Proving by induction,
Base case:
For n=1, a−b∣a1−b1
For proving induction step assume an−bn=k(a−b) such that k∈N.
Let L = an+1−bn+1 = an+1−abn+abn−bn+1
L = a(an−bn)+bn(a−b)
L = ka(a−b)+bn(a−b)
So L is divisible by a−b.
Hence proved by induction.
Ex6.1 Q13
Q. Prove that for all integers a and b and ∀n∈N, a+b∣a2n+1+b2n+1.
Soln.
Proving by induction,
Base case:
For n=1, a2(1)+1+b2(1)+1 = a3+b3.
a3+b3 = (a+b)(a2−ab+b2).
So divisible by a+b.
For proving induction step assume a2n+1+b2n+1 = k(a+b) such that k∈N.
Let L = a2(n+1)+1+b2(n+1)+1 = a2n+3+b2n+3
L = a2n+3+a2b2n+1−a2b2n+1+b2n+3
L = a2(a2n+1+b2n+1)−b2n+1(a2−b2)
L = ka2(a+b)−b2n+1(a+b)(a−b)
So L is divisible by a+b.
Hence proved by induction.
Ex6.1 Q14
Q. Prove that ∀n≥10, 2n>n3.
Soln.
Proving by induction,
Base case:
For n=10, 210=1024>1000=103
So 2n>n3 ∀n≥10
For proving induction step assume 2n>n3.
2n+1 = 2(2n) > 2n3 = n3+n3
n3+n3≥n3+10n2 (∀n≥10)
n3+10n2=n3+3n2+7n2
n3+3n2+7n2≥n3+3n2+70n (∀n≥10)
n3+3n2+70n=n3+3n2+3n+67n
n3+3n2+3n+67n≥n3+3n2+3n+1
So 2n+1>(n+1)3.
Hence proved by induction.
Ex6.2 Q7a
Q. Prove that if a and b are positive real numbers, then ba+ab≥2.
Soln.
Assume ba+ab<2
ba+ab<2 => ab(a2+b2)<2 => a2+b2<2ab
a2+b2<2ab => a2−2ab+b2<0
a2−2ab+b2<0 => (a−b)2<0
But ∀x∈R, x2≥0. This is contradictory.
Hence proved by contradiction.
Ex6.2 Q7b
Q. Suppose that a,b,c∈R and 0<a≤b≤c. Prove that cb+ac−ab≥1.
Soln.
c≥a => c−a≥0
c≥b => c−b≥0
(c−a)(c−b)≥0 => c2−bc−ac+ab≥0
c2−bc−ac+ab≥0 => ab+c2−bc≥ac
ab+c2−bc≥ac => ac(ab+c2−bc)≥1
ac(ab+c2−bc)≥1 => cb+ac−ab≥1
Hence proved.
Ex6.2 Q7c
Q. Prove that if n≥2 and a1,a2,...,an∈R such that 0<a1≤a2≤...≤an, then a2a1+a3a2+...+anan−1+a1an≥n.
Soln.
Proving by induction,
Base case:
a2a1+a1a2≥2
Proved previously.
For proving induction step assume a2a1+a3a2+...+anan−1+a1an≥n.
Adding an+1an−a1an+a1an+1 to both sides,
a2a1+a3a2+...+an+1an+a1an+1≥n+an+1an+a1an+1−a1an
But an+1an+a1an+1−a1an≥1 (proved previously). So,
a2a1+a3a2+...+anan−1+a1an≥n+1
Hence proved by induction.
Ex6.3 Q1
Q. Find a formula for i=1∑ni(i+1)1 and prove that your formula is correct.
Soln.
i=1∑ni(i+1)1=i=1∑ni(i+1)(1+i−i)
=i=1∑ni(i+1)(i+1)−i(i+1)i=i=1∑ni1−i+11
=(11+21+...+n1)−(21+...+n1+n+11)
=1−n+11=n+1(n+1)−n+11=n+1n.
Ex6.3 Q2
Q. Prove that ∀n≥1, i=1∑ni(i+1)(i+2)1=4(n+1)(n+2)(n2+3n).
Soln.
Proving by induction,
Base case:
For n=1,
LHS = i=1∑1i(i+1)(i+2)1=1(2)(3)1=61
RHS = 4(n+1)(n+2)(n2+3n)=4(2)(3)(1+3)=61
For proving induction step assume i=1∑ni(i+1)(i+2)1=4(n+1)(n+2)(n2+3n).
i=1∑n+1i(i+1)(i+2)1=(n+1)(n+2)(n+3)1+i=1∑ni(i+1)(i+2)1
=(n+1)(n+2)(n+3)1+4(n+1)(n+2)(n2+3n)
=(n+1)(n+2)1(4(n+3)4+4(n+3)(n3+6n2+9n))
=4(n+1)(n+2)(n+3)(n3+6n2+9n+4)
=4(n+1)(n+2)(n+3)(n+1)(n+1)(n+4)
=4(n+2)(n+3)(n2+5n+4)
=4(n+1+1)(n+1+2)(n2+2n+1+3n+3)
=4(n+1+1)(n+1+2)((n+1)2+3(n+1))
Hence proved by induction.
Ex6.3 Q3
Q. Prove that ∀n≥2, i=2∑n(i−1)(i+1)1=4n(n+1)(3n2−n−2).
Soln.
Proving by induction,
Base case:
For n=2,
LHS = i=2∑2(i−1)(i+1)1=1(3)1=31
RHS = 4(2)(3)(3(2)2−2−2)=248=31
For proving induction step assume i=2∑n(i−1)(i+1)1=4n(n+1)(3n2−n−2).
i=2∑n+1(i−1)(i+1)1
=n(n+2)1+i=2∑n(i−1)(i+1)1
=n(n+2)1+4n(n+1)(3n2−n−2)
=4n(n+1)(n+2)4(n+1)+4n(n+1)(n+2)(3n3+5n2−4n−4)
=4n(n+1)(n+2)(3n3+5n2)
=4(n+1)(n+2)(3n2+5n)
=4(n+1)(n+1+1)(3n2+6n+3−n−1−2)
=4(n+1)(n+1+1)(3(n+1)2−(n+1)−2)
Hence proved by induction.
Ex6.3 Q4
Q. Prove that ∀n∈N, i=0∑n(2i+1)2=3(n+1)(2n+1)(2n+3).
Soln.
Proving by induction,
Base case:
For n=1,
LHS = i=0∑1(2i+1)2=12+32=10
RHS = 3(2)(3)(5)=10
For proving induction step assume i=0∑n(2i+1)2=3(n+1)(2n+1)(2n+3).
i=0∑n+1(2i+1)2=(2(n+1)+1)2+i=0∑n(2i+1)2
=(2n+3)2+3(n+1)(2n+1)(2n+3)
=(2n+3)(3(6n+9)+3(2n2+3n+1))
=3(2n+3)(2n2+9n+10)
=3(n+2)(2n+3)(2n+5)
=3((n+1)+1)(2(n+1)+1)(2(n+1)+3)
Hence proved by induction.
Ex6.3 Q5
Q. Suppose r∈R and r=1. Prove that ∀n∈N, i=0∑nri=r−1(rn+1−1).
Soln.
Proving by induction,
Base case:
For n=1,
LHS = i=0∑1ri=r0+r1=1+r
RHS = r−1(r2−1)=r−1(r+1)(r−1)=r+1
For proving induction step assume i=0∑nri=r−1(rn+1−1).
i=0∑n+1ri=rn+1+i=0∑nri=rn+1+r−1(rn+1−1)
=r−1rn+1(r−1)+r−1(rn+1−1)
=r−1(rn+2−rn+1+rn+1−1)=r−1(rn+2−1)
=r−1(r(n+1)+1−1)
Hence proved by induction.
Ex6.3 Q6
Q. Prove that ∀n≥1, i=1∑ni21≤2−n1.
Soln.
Proving by induction,
Base case:
For n=1,
LHS = i=1∑1i21=121=1
RHS = 2−11=1
For proving induction step assume i=1∑ni21≤2−n1.
i=1∑n+1i21=(n+1)21+i=1∑ni21≤(n+1)21+2−n1
=2−(n(n+1)2(n+1)2−n(n+1)2n)
=2−n(n+1)2(n2+n+1)<2−n(n+1)2(n2+n)
=2−n(n+1)2n(n+1)=2−n+11
Hence proved by induction.
Ex6.3 Q8a
Q. Prove that ∀n,m∈N, if n≥m then Hn−Hm≥n(n−m).
Soln.
Proving by induction,
Let m be any arbitrary number.
Base case:
For n=m:
LHS = Hm−Hm=0
RHS = m(m−m)=0
For proving induction step assume Hn−Hm≥n(n−m).
Hn+1−Hm=n+11+Hn−Hm
≥n+11+n(n−m)=n+11+1−nm
=1+n(n+1)(n−n×m−m)
=1+n(n+1)(n−m)−n(n+1)(n×m)≥1−n+1m
Hence proved by induction.
Ex6.3 Q8b
Q. Prove that ∀n≥0, H2n≥1+2n.
Soln.
Proving by induction,
Base case:
For n=0:
LHS = H20=H1=i=1∑1i1=11=1
RHS = 1+20=1
For proving induction step assume H2n≥1+2n.
H2n+1=H2n+i=2n+1∑2n+1i1≥1+2n+i=2n+1∑2n+1i1
≥1+2n+2n(2n+11)=1+2(n+1)
Hence proved by induction.
Ex6.3 Q8c
Q. Show that n→∞limHn=∞, so i=1∑∞i1 diverges.
Soln.
H2n≥1+2n (proved previously)
n→∞limH2n≥n→∞lim(1+2n)
H2∞≥1+2∞
H∞=∞
i=1∑∞i1=∞
Hence it diverges.
Ex6.3 Q9
Q. Prove that ∀n≥2, k=1∑n−1Hk=nHn−n.
Soln.
Proving by induction,
Base case:
For n=2,
LHS = k=1∑2−1Hk=H1=11=1
RHS = 2H2−2=2(11+21)−2=3−2=1
For proving induction step assume k=1∑n−1Hk=nHn−n.
k=1∑nHk=Hn+k=1∑n−1Hk=Hn+nHn−n
=(n+1)Hn+1−n−1
=(n+1)Hn+n+1(n+1)−n−1
=(n+1)(Hn+n+11)−n−1
=(n+1)Hn+1−(n+1)
Hence proved by induction.
Ex6.3 Q10
Q. Find a formula for i=1∑ni(i!) and prove that your formula is correct.
Soln.
i=1∑ni(i!)=i=1∑n(i+1−1)(i!)
=i=1∑n(i+1)!−i!
=(2!+...+n!+(n+1)!)−(1!+2!+...+n!)
=(n+1)!−1.
Ex6.3 Q11
Q. Find a formula for i=0∑n(i+1)!i and prove that your formula is correct.
Soln.
i=0∑n(i+1)!i=i=0∑n(i+1)!(i+1−1)
=i=0∑n(i+1)!(i+1)−(i+1)!1=i=0∑ni!1−(i+1)!1
(0!1+1!1+...+n!1)−(1!1+...+n!1+(n+1)!1)
=1−(n+1)!1.
Ex6.3 Q12a
Q. Prove that ∀n∈N, 2n>n.
Soln.
Proving by induction,
Base case:
For n=1, 21>1
For proving induction step assume 2n>n.
2n+1=2(2n)>2n=n+n≥n+1
Hence proved by induction.
Ex6.3 Q12b
Q. Prove that ∀n≥9, n!≥(2n)2.
Soln.
Proving by induction,
Base case:
For n=9,
LHS = 9!=362880
RHS = (29)2=5122=262144
For proving induction step assume n!≥(2n)2.
(n+1)!=(n+1)(n!)≥(n+1)(2n)2
=(n+1)22n≥10(22n)>4(22n)=(2n+1)2
Hence proved by induction.
Ex6.3 Q12c
Q. Prove that ∀n∈N, n!≤2(n2).
Soln.
Proving by induction,
Base case:
For n=1,
LHS = 1!=1
RHS = 2(12)=2
For proving induction step assume n!≤2(n2).
(n+1)!=(n+1)(n!)≤(n+1)2(n2)
(n+1)2(n2)<2n+1×2(n2) (proved previously)
=2n2+n+1<2n2+2n+1=2(n+1)2
Hence proved by induction.
Ex6.3 Q13a
Q. Prove that ∀n∈N, (k2+n)!≥k2n.
Soln.
Proving by induction,
Base case:
For n=1,
LHS = (k2+1)!≥k2+1
RHS = k2
For proving induction step assume (k2+n)!≥k2n.
(k2+n+1)!=(k2+n+1)(k2+n)!
≥(k2+n+1)k2n>k2(k2n)=k2(n+1)
Hence proved by induction.
Ex6.3 Q13b
Q. Prove that ∀n≥2k2, n!≥kn.
Soln.
Proving by induction,
Base case:
For n=2k2,
LHS = (2k2)!=(k2+k2)!≥k2k2 (proved previously)
RHS = k2k2
For proving induction step assume n!≥kn.
(n+1)!=(n+1)(n!)≥(n+1)kn
≥(2k2+1)kn>(k)kn=kn+1
Hence proved by induction.
Ex6.3 Q15
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=0; ∀n∈N, an+1=2an+n. Prove that ∀n∈N, an=2n−n−1.
Soln.
Proving by induction,
Base case:
For n=0,
LHS = a0=0
RHS = 20−0−1=1−1=0
For proving induction step assume an=2n−n−1.
an+1=2an+n=2(2n−n−1)+n
=2n+1−2n−2+n=2n+1−n−1−1
=2n+1−(n+1)−1
Hence proved by induction.
Ex6.3 Q16
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=2; ∀n∈N, an+1=(an)2. Find a formula for an and prove that your formula is correct.
Soln.
Calculating values of sequence,
n | an |
|---|---|
0 | 2 |
1 | 4 |
2 | 16 |
From this we can assume an=22n.
Proving by induction,
Base case:
For n=0,
LHS = a0=2
RHS = 220=21=2
For proving induction step assume an=22n.
an+1=(an)2=(22n)2=22(2n)=22n+1
Hence proved by induction.
Ex6.3 Q17
Q. A sequence a1,a2,a3,... is defined recursively as follows: a1=1; ∀n∈N, an+1=an+1an. Find a formula for an and prove that your formula is correct.
Soln.
Calculating values of sequence,
n | an |
|---|---|
1 | 1 |
2 | 21 |
3 | 31 |
From this we can assume an=n1.
Proving by induction,
Base case:
For n=1,
LHS = a1=1
RHS = 11=1
For proving induction step assume an=n1.
an+1=an+1an=n1+1(n1)=n(n+1)(n1)=n+11
Hence proved by induction.
Ex6.3 Q20
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=0; ∀n∈N, an+1=an2+41. Prove that ∀n≥1, 0<an<1.
Soln.
Instead prove that ∀n≥1, 0<an<21.
Proving by induction,
Base case:
For n=1,
a1=a02+41=02+41=41
For proving induction step assume 0<an<21.
an+1=an2+41>0
an+1=an2+41<(21)2+41=21<1
Hence proved by induction.
Ex6.4 Q3a
Q. Prove that √6 is irrational.
Soln.
Assume that √6 is rational and can be written in simplified form as qp where p,q∈N.
qp=√6 => q2p2=6 => p2=6q2 (eq1)
This means that p must be even and can be written as p=2k where k∈N.
Substituting in eq1,
4k2=6q2 => 2k2=3q2
This means that q must also be even.
But qp was simplified form which contradicts.
Hence proved by contradiction.
Ex6.4 Q3b
Q. Prove that √2+√3 is irrational.
Soln.
Assume that √2+√3 is rational and can be written in simplified form as qp where p,q∈N. qp=√2+√3 => q2p2=5+2√6
=> 2q2(p2−5q2)=√6
√6 is irrational (proved previously) but LHS is rational which is a contradiction. Hence proved by contradiction.
Ex6.4 Q5
Q. Suppose that x∈R, x=0, and x+x1∈Z. Prove that ∀n≥1, xn+xn1∈Z.
Soln.
Consider a sequence ∀n≥1, an=xn+xn1.
Proving by induction,
Base cases:
For n=1, a1=x+x1∈Z
(x+x1)a1=x2+2+x21=a2+2
a2=(x+x1)a1−2∈Z
For proving induction step assume an−1,an∈Z.
(x+x1)an=xn+1+xn−11+xn−1+xn+11
(x+x1)an=an+1+an−1
an+1=(x+x1)an−an−1∈Z
Hence proved by induction.
Ex6.4 Q6a
Q. Prove that ∀n∈N, i=0∑nFi=Fn+2−1.
Soln.
Proving by induction,
Base case:
For n=0,
LHS = i=0∑0Fi=F0=0
RHS = F0+2−1=F2−1=1−1=0
For proving induction step assume i=0∑nFi=Fn+2−1.
i=0∑n+1Fi=Fn+1+i=0∑nFn=Fn+1+Fn+2−1
=Fn+3−1=F(n+1)+2−1
Hence proved by induction.
Ex6.4 Q6b
Q. Prove that ∀n∈N, i=0∑nFi2=FnFn+1.
Soln.
Proving by induction, Base case: For n=0, LHS = 0∑0Fi2=F0=0 RHS = F0F1=0×1=0 For proving induction step assume i=0∑nFi2=FnFn+1.
i=0∑n+1Fi2=Fn+12+i=0∑nFi2=Fn+12+FnFn+1 =Fn+1(Fn+1+Fn)=Fn+1F(n+1)+1 Hence proved by induction.
Ex6.4 Q6c
Q. Prove that ∀n∈N, i=0∑nF2i+1=F2n+2.
Soln.
Proving by induction, Base case: For n=0, LHS = i=0∑0F2i+1=F0+1=F1=1 RHS = F0+2=F2=1 For proving induction step assume i=0∑nF2i+1=F2n+2. i=0∑n+1F2i+1=F2(n+1)+1+i=0∑nF2i+1 =F2n+3+F2n+2=F2n+4=F2(n+1)+2 Hence proved by induction.
Ex6.4 Q6d
Q. Find a formula for i=0∑nF2i and prove that your formula is correct.
Soln.
i=0∑nF2i=F0+(F2+F4+...+F2n)
=0+(F0+F1+F2+...+F2n−1)
=i=0∑2n−1Fi=F2n−1+2−1 (proved previously)
=F2n+1−1.
Ex6.4 Q7a
Q. Prove that ∀m≥1 and ∀n∈N, Fm+n=Fm−1Fn+FmFn+1.
Soln.
Let n be any arbitrary number.
Proving by induction,
Base cases:
For m=1,
LHS = Fn+1
RHS = F1−1Fn+F1Fn+1=0+Fn+1=Fn+1
For m=2,
LHS = Fn+2
RHS = F1Fn+F2Fn+1=Fn+Fn+1=Fn+2
For proving induction step assume Fm−1+n=Fm−2Fn+Fm−1Fn+1 and Fm+n=Fm−1Fn+FmFn+1.
Fm+1+n=Fm+n+Fm−1+n
=Fm−1Fn+FmFn+1+Fm−2Fn+Fm−1Fn+1
=Fn(Fm−1+Fm−2)+Fn+1(Fm+Fm−1)
=FnF(m+1)−1+Fn+1Fm+1
Hence proved by induction.
Ex6.4 Q7b
Q. Prove that ∀m,n≥1, Fm+n=Fm+1Fn+1−Fm−1Fn−1.
Soln.
Let n be any arbitrary number.
Proving by induction,
Base cases:
For m=1,
LHS = Fn+1
RHS = F2Fn+1−F0Fn−1=Fn+1−0=Fn+1
For m=2,
LHS = Fn+2=Fn+1+Fn
RHS = F3Fn+1−F1Fn−1=2Fn+1−Fn−1
=Fn+1+Fn+Fn−1−Fn−1=Fn+1+Fn
For proving induction step assume Fm−1+n=FmFn+1−Fm−2Fn−1 and Fm+n=Fm+1Fn+1−Fm−1Fn−1.
Fm+1+n=Fm+n+Fm−1+n
=Fm+1Fn+1−Fm−1Fn−1+FmFn+1−Fm−2Fn−1
=Fn+1(Fm+1+Fm)−Fn−1(Fm−1+Fm−2)
=F(m+1)+1Fn+1−F(m+1)−1Fn−1
Hence proved by induction.
Ex6.4 Q7c
Q. Prove that ∀n∈N, Fn2+Fn+12=F2n+1 and Fn+22−Fn2=F2n+2.
Soln.
Part 1:
Fn2+Fn+12=F(n+1)−1Fn+Fn+1Fn+1
=F(n+1)+n (proved previously)
=F2n+1.
Part 2:
Fn+22−Fn2
=F(n+1)+1F(n+1)+1−F(n+1)−1F(n+1)−1
=F(n+1)+(n+1) (proved previously)
=F2n+2.
Ex6.4 Q7d
Q. Prove that ∀m,n∈N, if m∣n then Fm∣Fn.
Soln.
m∣n => n=km where k∈N.
Proving by induction,
Base case:
For k=1, Fm∣F1×m
For proving induction step assume Fm∣Fmk.
F(k+1)m=Fmk+m
=Fmk−1Fm+FmkFm+1 (proved previously)
=> Fm∣F(k+1)m
Hence proved by induction.
Ex6.4 Q8a
Q. Suppose c∈R and ∀n(an=cn). Prove that a0,a1,a2,... is a Gibonacci sequence iff c=2(1±√5).
Soln.
Proving first part,
a2=a1+a0 => c2=c+1 => c2−c−1=0
=> c=2(1±√5).
Proving second part,
c=2(1+√5) => c2=2(3+√5)
c2=1+2(1+√5)=1+c
an=cn=cn−2c2=cn−2(1+c)=cn−2+cn−1
an=an−1+an−2.
Ex6.4 Q8b
Q. Suppose s,t∈R, and ∀n∈N, an=s(2(1+√5))n+t(2(1−√5))n. Prove that a0,a1,a2,... is a Gibonacci sequence.
Soln.
an=s(2(1+√5))n+t(2(1−√5))n
=s(2(1+√5))n−2(2(1+√5))2+t(2(1−√5))n−2(2(1−√5))2
=s(2(1+√5))n−2(1+2(1+√5))+t(2(1−√5))n−2(1+2(1−√5))
=s(2(1+√5))n−2+s(2(1+√5))n−1+t(2(1−√5))n−2+t(2(1−√5))n−1
=an−2+an−1.
Ex6.4 Q8c
Q. Suppose a0,a1,a2,... is a Gibonacci sequence. Prove that there ∃s,t∈R such that ∀n∈N, an=s(2(1+√5))n+t(2(1−√5))n.
Soln.
Let s,t be any arbitrary real numbers.
Proving by induction,
Base cases:
For n=0,
a0=s(1)+t(1)=s+t
For n=1, a1=s(2(1+√5))+t(2(1−√5))
For proving induction step assume an−1=s(2(1+√5))n−1+t(2(1−√5))n−1 and an=s(2(1+√5))n+t(2(1+√5))n.
an+1=s(2(1+√5))n+1+t(2(1−√5))n+1
=s(2(1+√5))n−1(2(1+√5))2+t(2(1−√5))n−1(2(1−√5))2
=s(2(1+√5))n−1+s(2(1+√5))n+t(2(1−√5))n−1+t(2(1−√5))n
=an−1+an
Hence proved by induction.
Ex6.4 Q9
Q. The Lucas numbers(named for the French mathematician Edouard Lucas (1842–1891)) are the numbers L0,L1,L2,... defined as follows: L0=2; L1=1; ∀n≥2, Ln=Ln−2+Ln−1. Find a formula for Ln and prove that your formula is correct.
Soln.
Assume ∃s,t∈R where Ln=s(2(1+√5))n+t(2(1−√5))n (proved previously).
L0=2 => s+t=2 (eq1)
L1=1
=> s(2(1+√5))+t(2(1−√5))=1
=> 2(s+t)+2√5(s−t)=1
=> 2√5(s−t)=1−22=0
=> s−t=0 (eq2)
=> s=t=1 (from eq1,eq2)
=> Ln=(2(1−√5))n+(2(1−√5))n.
Ex6.4 Q10
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=−1; a1=0; ∀n≥2, an=5an−1+6an−2.
Find a formula for an and prove that your formula is correct.
Soln.
Assume ∀n∈N(an=cn). (Gibonacci form)
a2=5a1+6a0 => c2=5c+6
=> c2−5c−6=0 => c=3,2
So an=s(3n)+t(2n).
a0=−1 => s+t=−1 (eq1)
a1=0 => 3s+2t=0 (eq2)
=> (s,t)=(2,−3) (from eq1,eq2)
=> an=2(3n)−3(2n).
Ex6.4 Q11
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=0; a1=1; a2=1; ∀n≥3, an=21an−3+23an−2+21an−1. Prove that ∀n∈N, an=Fn, the nth Fibonacci number.
Soln.
an=21an−3+23an−2+21an−1
=21(an−3+an−2)+21an−1+an−2
=an−1+an−2=Fn.
Ex6.4 Q19
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=1; ∀n∈N, an+1=1+i=0∑nai. Find a formula for an and prove that your formula is correct.
Soln.
Calculating values of sequence,
n | an |
|---|---|
0 | 1 |
1 | 2 |
2 | 4 |
From this we can assume an=2n.
Proving by induction,
Base case:
For n=0, a0=1=20
For proving induction step assume an=2n.
an+1=1+i=0∑nai=1+i=0∑n2i=1+2n+1−1
=2n+1
Hence proved by induction.
Ex6.4 Q20
Q. A sequence a0,a1,a2,... is defined recursively as follows: a0=1; ∀n∈N, an+1=1+an1.
Find a formula for an and prove that your formula is correct.
Soln.
Calculating values of sequence,
n | an |
|---|---|
0 | 11 |
1 | 12 |
2 | 23 |
From this we can assume an=Fn+1Fn+2.
Proving by induction,
Base case:
For n=0, a0=1=11=F1F2.
For proving induction step assume an=Fn+1Fn+2.
an+1=1+an1=1+Fn+1Fn+21=1+Fn+2Fn+1
=Fn+2(Fn+2+Fn+1)=Fn+2Fn+3=F(n+1)+1F(n+1)+2
Hence proved by induction.