Answers>Maths>IB>Article

How does proof by induction work?

When using proof by induction we most often prove a statement P for positive integers n. We think about the problem in a domino-toppling fashion. The first step is to write out P(n=1), so inserting 1 for n in P. Showing that the left hand side LHS equals the right hand side RHS will prove P for n=1, so P(1). In the second step we assume that P is true for some positive integer k, so P(n=k). We write k instead of n into LHS and RHS. In the third step we evaluate P(n=k+1), so we plug in k+1 to the LHS, and use step 2 to rearrange the expression. Through rearranging we show that LHS of P(n=k+1) equals the RHS expected when plugging in k+1 into P. These 3 parts connect to form a proof for all n. Since we can say k=1, and we showed P(k+1) is true if P(k) is true (and we know P(k)=P(1) is true), we can say P(2) is true. Then repeating this mechanism means that P(3), P(4), P(5), ... are all true, thereby proving P(n) for all positive integers n.

Answered by Ana C. Maths tutor

1227 Views

See similar Maths IB tutors

Related Maths IB answers

All answers ▸

Solve the equation log(1-x) - log(x) = 1 where log() is the logarithmic function, base 10.


How to find a modulus and argument of w that is a quotient of z1 and z2 such that z1 = 1 + root(3)i and z2 = 1+ i using modulus-argument form?


Integrate x^2/(1+x^2)dx


Given h(x) = 9^x + 9 and g(x) = 10*3^x, find {x | h(x) < g(x)}.


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo
Cookie Preferences