Problem 23E
Devise a recursive algorithm for computing n2 where n is a nonnegative integer, using the fact that (n + 1)2 = n2 + 2n + 1. Then prove that this algorithm is correct.
Discrete Mathematics CS225 Terms and concepts: Week 2 Reading 145-159, 165-167. 183-184. 201-203 and Lectures and Supplemental Info List of Types of Numbers: • Natural numbers ( ℕ ): Counting numbers. {0, 1, 2, 3…} • Integers ( ℤ ): Positive and negative counting numbers. {…-2, -1, 0, 1, 2, …} • Rational numbers ( ℚ ): Numbers that can be expressed as a ratio of an integer to a non-zero integer. ◦ Quotients of integers. ◦ All integers are rational, but not all rational numbers are integers. • Real numbers ( ℝ ) : Numbers that have decimal representations. ◦ Can be positive, negative, or zero. ◦ All rational numbers are real, not all real numbers are rational. • Irrational numbers (I): Real numbers that are not rational. Elementary Number Theory and Methods of Proof • Theorem:Amathematical statement that is true. • Proof:Arigorous argument that a theorem is true. • Formal Proof: Manipulate logic expressions via mechanical rules of inference. ◦ Computers produce these. • Informal Proof:Argument stated in natural language. ◦ The argument must still be rigorous and sound. ◦ Mathematicians produce these. • An example involving a concept used frequently in CS. ◦ Floor of x ( ⌊x⌋ ): Greatest integer of x. The largest integer that is less than or equal to x. ▪ On the number line, ⌊x⌋ is the integer immediately to the left of x (or equal to x if x itself is an integer). • Ex: ◦ ⌊2.3⌋=2