Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

About an exercise appearing in TAOCP volume one's "Notes on the Exercises"

There is a question in TAOCP vol 1, in "Notes on Exercises" section, which goes something like:

"Prove that 13^3 = 2197. Generalize your answer. (This is a horrible kind of problem that the author has tried to avoid)."

Questions:

  1. How would you actually go about proving this ? (Direct multiplication is one way, another way could be using formula of (a+b)^3). Does the solution requires using some method that will allow us to make some kind of generalization ?

  2. What is the generalization here ?

  3. Why is this a horrible kind of problem ?

  4. What are some other kind of similar horrible problems that you are aware of ?

Appreciate any answers.

P.S. I apologize if the statement of problem above makes it look like a homework problem, but its not. Request people to not tag this as a homework problem, so that more people can give answers.

like image 286
vshenoy Avatar asked Oct 05 '09 07:10

vshenoy


2 Answers

I'd guess that he's alluding to perhaps proving it starting from just the Peano axioms. Then constructing the integers, and going on to formally show that 13^3 = 2197 is a natural, logical conclusion that flows from the definition of exponentiation.

We could generalize to show that given an a and b, there exists some integer c, that is a^b.

This is a horrible kind of a problem because most people find it uninteresting.

Similar sorts of problems can be found in a course on analysis (along with some greatly more interesting).

like image 174
garethm Avatar answered Nov 09 '22 08:11

garethm


I initially considered it as follows:
n3 = n * n * n
logn(n3) = logn(n*n*n)
logn(n3) = logn(n) + logn(n) + logn(n)
3 = 1 + 1 + 1
3 = 3

This seems fairly circular in its use of logarithmic identities, but given where I'm at in my algorithms research, it was oddly comforting.

like image 2
Stuart Thiel Avatar answered Nov 09 '22 10:11

Stuart Thiel