0

I have a function computes n^(2n) and I need to prove by it by induction. Here it is in python:

def n_to_2n(n):
    product = 1
    counter = n
    while counter > 0:
        product = product * n * n
        counter -= 1
    return product

I believe I've found a useful loop invariant: product = n^(2*(n - counter)). For initialization and termination, this LI is trivial to prove, but I'm having difficulty proving the maintenance stage by induction. There's two variables, so which one do I perform induction on? I tried on n but didn't get anywhere really.

Assume LI(n) holds, prove LI(n + 1): ???

steven
  • 103
  • I believe you should use the fact that result is n^(a_n) at any n and prove by induction only the fact that a_n=2n. – Ivan Kaznacheyeu Sep 20 '21 at 15:55
  • 1
    Prove that for all $i$ such that $0 \leq i \leq n$, after the $i$th iteration of the while loop, counter is $n - i$ and product is $n^{2i}$. – Mark Saving Sep 20 '21 at 15:56

0 Answers0