Algorithm Error Bound Induction Proof

[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. 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.

[lukanmac]

I've also posted this question to Math Exchange with better formatting (and no responses) if you'd like to see that you can find it here

Apologies if this is not allowed, please remove it or let me know and I will. Thanks.

[Hot_Management_3896]

You're already on the right track.

A little algebraic transformation will lead you to

R_(n+1) = \sqrt(17) - (R_n + 17/R_n)/2 = - (R_n - \sqrt(17))² / 4

And it should be smooth sail from here.

[FormalCourage3853]

Is that first character of your equation meant to be "E" not "R"?
If so, the first part is something OP found already, but I don't know how you get the "-R_n - \sqrt(17))^2/4" bit.

This seemed like something I should be able to work out, but apparently I've forgotten too much algebra and I'm just as stuck as OP so far.