2.4 number 1
1.a x(n) =x(n-1)+ 5 n>1 x(1)=0
Forward: x(2)=5, x(3)=10, x(4)=15=3*5 which suggests x(n)=(n-1)*5 so plug this is to verify: (n-1)*5 = (n-2)*5 +5 =(n-1)*5
Backward: x(n)=x(n-2) +5 +5 = x(n-3 )+5 +5 +5 =x(n-3)+3*5 suggests
x(n)=x(n-i)+i*5 which implies
x(n)=x(n-(n-1))+(n-1)*5= x(1)+(n-1)*5=(n-1)*5 by initial conditions
b. x(n)=3x(n-1) for x>1, x(1)=4
Backwards : x(n)=3*3*x(n-2)= 33x(n-3)==3ix(n-i)=3(n-1)x(n-(n-1))= 3(n-1)x(1)= 3(n-1)4
c.x(n)=x(n-1)+n for n>0 x(0)=0
x(n)=x(n-2)+n-1+n= x(n-3)=n-2+n-1+n = x(n-i)+ i+1 + i+2 +…n= x(0)+ 1+2+3+… n
=n(n+1)/2 Look at appendix A
d. x(n)=x(n/2)+n for n>1 x(1)=1 for n=2k
Forward:
x(2)=1 +2
x(4) = 1 + 2 + 4
x(8)= 1 + 2 +4 +8 = 20 + 21 + 22 + 23 suggests
x(2k) = 20 + 21 + 22 +… + 2k= (2k+1-1) by formula 5 p. 414
= (2n-1)
Plugging in gets (2n -1) = 2(n/2)-1 + n =2n -1 which works
e.x(n) =x (n/3) +1 for n>1 x(1) =3
Backwards:
x(3k) = x( 3k-1)+1 = x( 3k-2)+1+1 = x( 3k-3)+1+2= x( 3k-3)+3= x( 3k-k)+k = 1 +k
Or x(n) = 1 + log3(n)
4.
a.Q(n) =Q(n-1)+2n -1 for n>1; Q(1) =1
Looks like Q(2) =1+2*2-1=4
Q(3)=4+6-1=9
Q(4) = 9 +8-1 =16
Suggests Q(n)=n2.
Plugging this in yields n2= (n-1)2+ 2n-1 = n2-2n +1 +2n -1 = n2, i.e. it works
b. Let m(n) =Number of multiplications at step n
m(n)=m(n-1) +1; m(1) =0
m(n) = m(n-2) +2 =m(n-3)m +3 = m(n-(n-1)) + n-1 = m(1) +n-1 = n-1
c. Let C(n)= numbers of addition and subtractions,
C(n) = C(n-1) +2 which by 1.a suggests. C(n) =2*(n-1)
7.a.Algorithm twon(n)
if (n==0) return 1
else
return twon(n-1) + two(n-1)
b.Let a(n) = number of additions.
a(n) = 2*a(n-1) +1; a(0) =0
a(n) = 2*(2a(n-2) +1 ) +1=22a(n-2) +2 + 1= 23a(n-3) +4+2+1= 2na(n-n)+ 2(n-1)+ 2n-2+..2+ 1
=1 +2 +……2n-1= 2n-1
c. n
n-1 n-1
n-2 n-2 n-2 n-2
…………
1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0
d. Much , much worse than just multiplying an accumulator by 2 n times
10. Let m(n) be the number of multiplications. The algorithm calls a determinant function of one lower order n times and each time the results is multiplied by a number. IUf we do not include the multiplication by s, which is either +1 or -1. then
m(n)=n*m(n-1) +n for n>1 and m(1) =0
bSince factorial function is f(n)= nf(n-1), this grows faster
which says one should not use the determinant to solve a system of linear equations.