by 
whizkib
ANSWERS: 2
-
You're trying prove P(n) for numbers n, where P is the property you are trying to prove. You do this by first proving P for some low value of n. Then assume you have proved it for P(n) and use that in your proof for P(n+1). A typical example is prove that the sum of the cubes from 1 to n is equal to the square of the sum of the numbers from 1 to n: 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + 4 + ... + n)^2 Clearly it's true for P(1) since the sum of the cubes is 1 and the square of the sum of the numbers is 1. This is the "base case". Assume that it's true for n. So we assume the above long equation is true Now given that, have to prove that it is true for n+1. Let S stand for 1+2+...+n In the long equation for n+1: The left hand side will increase by (n+1)^3 The right hand side will increase by 2 S (n+1) + (n+1)^2 If the property is true for n+1, then these will be equal. You may know that S = (n *(n+1))/2 So 2*S = n*(n+1) 2*S*(n+1) + (n+1)^2 = n*(n+1)^2*n (n+1)^2 = (n+1)*(n+1)^2 = (n+1)^3 So its true for all n >= 1 (the starting case) [If you didn't know about the formula for S, try proving it by induction!]
-
"The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps: The basis: showing that the statement holds when n = 0. The inductive step: showing that if the statement holds for n = m, then the same statement also holds for n = m + 1. " Source and further information: http://en.wikipedia.org/wiki/Mathematical_induction (there you can also find some examples)
iwnit RELATED QUESTIONS
Copyright 2023, Wired Ivy, LLC