How to prove that this while loop calculates n^2 - Software Engineering Stack Exchange most recent 30 from softwareengineering.stackexchange.com 2019-08-22T19:21:49Z https://softwareengineering.stackexchange.com/feeds/question/269909 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://softwareengineering.stackexchange.com/q/269909 1 How to prove that this while loop calculates n^2 Pieter Verschaffelt https://softwareengineering.stackexchange.com/users/164294 2015-01-13T09:19:34Z 2015-01-13T18:13:27Z <p>I'm studying for my exam of logic later this week and I have to prove that this while loop:</p> <pre><code>i := 0 s := 0 while i &lt; n do i := i + 1 s := s + (2*i -1) </code></pre> <p>calculates n^2. This question is made up of 2 subquestions. We have to prove that 0 ≤ i ≤ n ∧ s = i^2 is a loop invariant for this while loop. I managed to prove that, but the second subquestion is that I have to prove that this loop calculates n^2, but I don't really know how to start. The course is a bit confusing about this part of the question.</p> https://softwareengineering.stackexchange.com/questions/269909/how-to-prove-that-this-while-loop-calculates-n2/269911#269911 10 Answer by Julia Hayward for How to prove that this while loop calculates n^2 Julia Hayward https://softwareengineering.stackexchange.com/users/43098 2015-01-13T09:24:35Z 2015-01-13T09:24:35Z <p>The loop calculates 1 + 3 + 5 + 7 + ... + (2n-1). The easiest way to visualise that this sums to n^2 is <img src="https://i.stack.imgur.com/fo0xl.png" alt="enter image description here"></p> https://softwareengineering.stackexchange.com/questions/269909/how-to-prove-that-this-while-loop-calculates-n2/269913#269913 3 Answer by ratchet freak for How to prove that this while loop calculates n^2 ratchet freak https://softwareengineering.stackexchange.com/users/25768 2015-01-13T09:40:13Z 2015-01-13T09:40:13Z <p>Using the formula of <a href="https://en.wikipedia.org/wiki/Arithmetic_progression" rel="nofollow">arithmetic progression</a> we can derive it directly:</p> <p>number of elements is <code>n</code>, first element is <code>1</code> last element is <code>2*n-1</code></p> <pre><code>n*(1 + 2*n-1)/2 = n*(2*n) /2 = n*n </code></pre> https://softwareengineering.stackexchange.com/questions/269909/how-to-prove-that-this-while-loop-calculates-n2/269925#269925 1 Answer by Benjamin Rickels for How to prove that this while loop calculates n^2 Benjamin Rickels https://softwareengineering.stackexchange.com/users/108376 2015-01-13T12:13:31Z 2015-01-13T12:13:31Z <p>You could also prove this by a method called 'mathematical induction', which works for positive integers.</p> <p>To put it simply: You assume that you statement about the loop is true for a arbitrary 'n' and so it's also true for 'n+1' and therefore for every integer bigger than your lower border (which normally is 1, but in your case, 0 works as well).</p> <p>It's a way more mathematical approach and so you may like it or you hate it. But here we go:</p> <p><img src="https://i.stack.imgur.com/esdC8.jpg" alt=""></p> <p>If you're not familiar with the sigma operator in mathematics, this is how it works. It's simply a 'for' loop, with 'a' being the starting value and 'b' being the included upper limit. It increases 'a' every 'iteration' by one and sums the values together.</p> <p>So mathematically, your problem could be written like this:</p> <p><img src="https://i.stack.imgur.com/S2azI.jpg" alt=""></p> <p>Now, for mathematical induction to work, we first have to prove that this statement is true for the lowest value of 'n' (this would normally be 1, but 0 works here as well):</p> <p><img src="https://i.stack.imgur.com/KfQ60.jpg" alt=""></p> <p>Which definitely is true.</p> <p><img src="https://i.stack.imgur.com/T0TKl.jpg" alt=""></p> <p>And thats true as well.</p> <p>Great, so let's move on to the 'exciting' part... Proving this statement for any (positive integer) 'n' by replacing 'n' with 'n + 1':</p> <p><img src="https://i.stack.imgur.com/NUXXU.jpg" alt=""></p> <p>Now, this looks quite complicated, but let's analyse it step by step. The first part is exactly the same as in the second picture, but now every 'n' is replaced by 'n + 1'. The second part (after the '->' and there especially the left side of the equation) may not be obvious at the first glance. But from a programmers point of view it might be a bit easier to understand, because</p> <pre><code>for(int i = 0; i &lt;= n; i++) { ...Do sth here. } </code></pre> <p>is exactly the same as</p> <pre><code>for(int i = 0; i &lt;= l; i++) { ...Do sth here (part 1) } for(int i = l + 1; i &lt;= n; i++) { ...Do sth here (part 2) } </code></pre> <p>On the right side of the equation I simply expanded '(n + 1)^2' to 'n^2 + 2n + 1'. Now the final spurt:</p> <p><img src="https://i.stack.imgur.com/GaPNv.jpg" alt=""></p> <p>Since for our second 'loop' (=sigma operator) the upper value equals the lower value, we don't need it at all. There's only one iteration with this particular value, so we simply can replace 'k' with 'n + 1', which then gives us '2*(n + 1) - 1'. So we now have still the same sigma left, which we had in the beginning and we wanted to prove being 'n' squared. So to get rid of it, we simply can replace it by 'n^2' in the second part (after the '->'), because if our assumption is true, there is no difference between them. We now have 'n^2' on both sides, so we can simply subtract it to get rid of it as well.</p> <p><img src="https://i.stack.imgur.com/gvvQp.jpg" alt=""></p> <p>So whats now left we can simply out multiply and eventually get an equation, which is true as well. Therefore we have proven that a loop summing up all odd numbers (starting from 1 up to '2n - 1') equals 'n^2'.</p> https://softwareengineering.stackexchange.com/questions/269909/how-to-prove-that-this-while-loop-calculates-n2/269956#269956 2 Answer by Michael Shaw for How to prove that this while loop calculates n^2 Michael Shaw https://softwareengineering.stackexchange.com/users/72188 2015-01-13T18:13:27Z 2015-01-13T18:13:27Z <p>Existing answers have missed an important point: the OP has already proved some things, and the practice exam question asked him to prove these things first. Presumably, this is because the things he's already proved are meant to be handy stepping stones towards finishing the proof. </p> <p>We want to prove that the program outputs n^2. Since there are no output statements, presumably one of the variables is the output, and it isn't <code>i</code>, so it must be <code>s</code>. </p> <p>We already have s=i^2, so we're actually really close; wouldn't it be nice if i=n at the end of the loop? Turns out, i=n is true at the end of the loop. And we're done. </p> <p>When proving things, it's very often helpful to look at other things we've already proved and what we're trying to prove. Similarities between what we have and what we want can be suggestive of things to try. </p>