Answer to Question #95607 in Discrete Mathematics for Ahmed

Question

Consider the sequences (rn) and (sn) defined recursively by
r0 = 1, s0 = 0, and rn+1 = rn/2, sn+1 = sn + rn+1 for n ≥ 0.
(a) What are the formulas for the nth terms rn and sn of these sequences?
(b) What is the floating point binary representation of sn?
(c) Write a MATLAB program which generates the sequences (rn) and (sn) recursively, and
run it on your computer until the computed values satisfy sn+1 = sn. To do this you can
use a for loop with a break statement. Display the sequence of values of n and sn in two
columns.
(d) What does this tell you about the storage of real numbers in your computer (assuming it
uses binary representation)?

Answer 1

(a) rn = 2^(-n), sn = 1 - 2^(-n)

(b) 001111111110 (1) n-1 times and (0) 53-n times

example for n = 4

0011111111101110000000000000000000000000000000000000000000000000

(c)

>> r = 1;

s = 0;

for n = 0:100

  fprintf('n = %g, sn = %24.20g\n',n,s)

  r = r/2;

  s1 = s + r;

if s1 ~=s

    s = s1;

  else

    break;

  end;

end;

n = 0, sn =            0

n = 1, sn =           0.5

n = 2, sn =           0.75

n = 3, sn =          0.875

n = 4, sn =          0.9375

n = 5, sn =         0.96875

n = 6, sn =         0.984375

n = 7, sn =        0.9921875

n = 8, sn =        0.99609375

n = 9, sn =       0.998046875

n = 10, sn =       0.9990234375

n = 11, sn =      0.99951171875

n = 12, sn =      0.999755859375

n = 13, sn =     0.9998779296875

n = 14, sn =     0.99993896484375

n = 15, sn =    0.999969482421875

n = 16, sn =    0.9999847412109375

n = 17, sn =   0.99999237060546875

n = 18, sn =   0.999996185302734375

n = 19, sn =  0.9999980926513671875

n = 20, sn =  0.99999904632568359375

n = 21, sn =  0.99999952316284179688

n = 22, sn =  0.99999976158142089844

n = 23, sn =  0.99999988079071044922

n = 24, sn =  0.99999994039535522461

n = 25, sn =  0.9999999701976776123

n = 26, sn =  0.99999998509883880615

n = 27, sn =  0.99999999254941940308

n = 28, sn =  0.99999999627470970154

n = 29, sn =  0.99999999813735485077

n = 30, sn =  0.99999999906867742538

n = 31, sn =  0.99999999953433871269

n = 32, sn =  0.99999999976716935635

n = 33, sn =  0.99999999988358467817

n = 34, sn =  0.99999999994179233909

n = 35, sn =  0.99999999997089616954

n = 36, sn =  0.99999999998544808477

n = 37, sn =  0.99999999999272404239

n = 38, sn =  0.99999999999636202119

n = 39, sn =  0.9999999999981810106

n = 40, sn =  0.9999999999990905053

n = 41, sn =  0.99999999999954525265

n = 42, sn =  0.99999999999977262632

n = 43, sn =  0.99999999999988631316

n = 44, sn =  0.99999999999994315658

n = 45, sn =  0.99999999999997157829

n = 46, sn =  0.99999999999998578915

n = 47, sn =  0.99999999999999289457

n = 48, sn =  0.99999999999999644729

n = 49, sn =  0.99999999999999822364

n = 50, sn =  0.99999999999999911182

n = 51, sn =  0.99999999999999955591

n = 52, sn =  0.99999999999999977796

n = 53, sn =  0.99999999999999988898

n = 54, sn =            1

(d) double-precision format can be used to store 53 binary digits or approximately 16 decimal digits of a number in decimal format.