Question

(14) Given a sequence of integers {fi,f2 /. defined by the following recursive function f (n)-., n e N such that s(2) 5, Evamine the sruture of this sequence and then compute J, in closed-form.Prove by using strong induction as discussed in class that your function f, is indeed correct.

Answer 1

IT has general solution of the form f(n)=r^n
Substituting gives

r^2=2r-1

r^2-2r+1=0

r=1,repeated roots

f(n)=1^n(A+Bn)=A+Bn

f(1)=A+B=1

f(2)=A+2B=5

B=4,A=-3

f(n)=-3+4n

Proof using structural induction

Base case:n=2

f(2)=-3+4*2=5

So base case is true

Inductive hypothesis: Assume true for all 2<=k<=n for some n>=2

Inductive step: We show it is true for n+1

f(n+1)=2f(n)-f(n-1)=2(-3+4n)-(-3+4(n-1))=-6+8n+3-4(n-1)=-3+4n+4=-3+4(n+1)

HEnce true for n+1 and hence for all n>=2