It should now be safe to say that the recursive form of G(n) from the problem unraveled to 30 + 31 + 32 + ... + 3n, which some may recall is also known as geometric series, or geometric progression. This is a very common type of expression, which was introduced all the way in high school. Since that was such a long time ago, I completely forgot all about it, and was sitting clueless trying to come up with a closed form for that expression.
The phrase "geometric series" never dawned on me. Much like with "closed form" of the Fibonacci sequence earlier, that made all my googling fruitless, as I was searching for "sum of powers" and the like instead.
So here is my better derivation of the closed form, very much in a computer scientist's way:
Notice that if we replace 3's with 2's, we get a way of showing a number 1111...12, that is a binary string of n 1's. So our G(n) really is 1111...13, that is a tertiary string of n 1's. We can also see that 2222...23 is in fact 1 less than 3n+1, and 2 times more than 1111...13. So
2222...23 = 3n+1 - 1 = 2 * 1111...13 = 2* G(n)
So G(n) = (3n+1 - 1) / 2
Now, if this isn't the neatest way of deriving a formula for geometric series, I don't know what is. It is also pretty easy to extend the reasoning to a generic case of base other than 2 or 3.
3 comments:
That is a very nifty proof (I think removing the "replace 3 by 2" would make it better).
Although, how do you know that
x=22...2_3 (where x's base 3 representation has n digits) is in fact, 3^(n+1)-1? I mean, x's base 3 representation (i.e. 22...2_3) is defined as
Sigma(from i=0; to i=n; 2*3^i)=
2*Sigma(from i=0; to i=n; 3^i) and so saying that it is equal to 3^(n-1)-1 is pretty much assuming what you're set out to prove.
There's a typo on the second last line there. It's supposed to be 3^(n+1)-1, not 3^(n-1)-1
The reason I presume that x=22...2_3 (where x's base 3 representation has n digits) is in fact, 3^(n+1)-1 is because if you add that 1 to it, all the 2's will have a carry so the will all flip to zeros and we'll get 1 as the additional first character. Which is to say, we'll get a total of 3^(n+1). The way I phrase it does not sound very scientific, but I suppose a more skillful computer scientist could adjust the wording to be more rigorous and convincing. Although from the common sense point of view it is quite convincing as is (to me at least).
Post a Comment