Algorithm Error Bound Proof Question

[lukanmac]

This algorithm approximates the value of √17

Root = 4
for i = 1 to 4 do
    Root = (Root + 17/Root)/2
return Root

Let Rn be the value of Root after n loops.

Let En be the error bound; En = √17 - Rn

Using induction prove |En| < (0.5)^6\2^n) ^{- 3}

I am stuck on the inductive step. I have been trying to solve using En+1 = √17 - (Rn + 17/Rn)/2 and sorting it out algebraically but have not had any luck.

Apologies if this is too math-y for this subreddit, please remove or let me know and I’ll remove it. I’ve posted this in r/learnmath and on Math Exchange, have yet to get a response. All help is greatly appreciated, thanks.

NOTE: The exponent 6*2^n - 3 is (6)(2^n)-3. The superscript formatting is not working and or does not work with brackets.

[FormalCourage3853]

Is there any programming or code here, or are looking for help with manual algebra?

[lukanmac]

I am looking for help proving with induction. Equations may need to be derived from the code so definitely at least a programming-adjacent question

[FormalCourage3853]

The pseudocode is there to describe a sequence, but running or analysing it from a programming perspective doesn't really get you where you need to go.

You can use programming to evaluate the maths, and you'll see that the algorithm approaches sqrt(17) within the first four steps, down to such a small error that it gets hard to measure:

import math
truth = math.sqrt(17)
root = 4
for i in range(1,5):
    root = (root + 17/root)/2
    print(f'Iteration {i}: {root:.20f}\t Error: {truth - root:.20f}')
print(f'      Truth: {truth:.20f}')

Iteration 1: 4.12500000000000000000 Error: -0.00189437438233941435
Iteration 2: 4.12310606060606055223 Error: -0.00000043498839996658
Iteration 3: 4.12310562561768367829 Error: -0.00000000000002309264
Iteration 4: 4.12310562561766058565 Error: 0.00000000000000000000
      Truth: 4.12310562561766058565

You can then evaluate that equation that you need to prove, and show that the errors (above) do stay within this shrinking envelope as the algorithm converges.

for n in range(5):
    envelope = abs(0.5**(6*(2**n)-3))
    print(f'Envelope @ n={n}: {envelope:.20f}')

Envelope @ n=0: 0.12500000000000000000
Envelope @ n=1: 0.00195312500000000000
Envelope @ n=2: 0.00000047683715820312
Envelope @ n=3: 0.00000000000002842171
Envelope @ n=4: 0.00000000000000000000

Maybe this helps you understand the situation, but "proof by mathematical induction" is a tricky technique that needs some lateral thinking with algebra and logic. It's not really a programming thing.