SEARCH HOME
 Math Central Quandaries & Queries
 Question from Tim, a student: I am trying to understand a^(2^n). The hint they give is a^(2^(n+1)) = (a^(2^n))^2 I am writing a program that will solve a^(2^n) recursively but need to understand the power before I begin. I am currently pursuing writing (a) x (a^(2^(n-1))) where the (a^(2^(n-1))) would be the recursive function call a n approaches 0. Once n is 0, the result would be multiplied by a two more times. Anyway, explaining these powers would be appreciated. I will most likely complete the program before the answer but I want to understand the logic of these powers. Thank you, Tim

Hi Tim. I hope I understand what you are trying to accomplish. I will proceed with the assumption n is a non-negative integer.

    var p = a;            // let p represent the product
for (; n>0; n--) {
p = p^2;
}
print p;


This code uses the hint. When n = 0, then p = a^(2^0) which is a^1, so we start at p = a. For each higher value of n, the product is squared again. That's what is implied by the hint a^(2^(n+1)) = (a^(2^n))^2. So this little snippet of code uses a decrement loop such as one it sounds like you were leaning toward.

However, the code above is not recursive; rather, it is iterative. So here's a less obvious bit of code that is recursive:

   // calculate p = a^(2^n) using a function that is recursive.
p = f(a,n);

function f(a,n) {
if (n > 0) {
var i = f(a,n-1);       // get the value for n-1
return i*i;             // and square it because a^(2^n) = [ a^(2^(n-1)) ]^2
} else {
return a;               // because a^(2^0) = a
}
}



Hope this helps,
Stephen La Rocque.

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.