- WELCOME TO INTRODUCTION TO MATHEMATICAL INDUCTION.
THE GOAL OF THIS VIDEO IS TO PROVE A MATHEMATICAL STATEMENT
USING INDUCTION.
MATHEMATICAL INDUCTION IS THE METHOD TO PROVE
THAT A GIVEN STATEMENT IS TRUE FOR ALL NATURAL NUMBERS,
AND THERE ARE TWO STEPS TO THE MATHEMATICAL INDUCTION PROCESS.
THE FIRST STEP IS THE BASIS WHERE WE SHOW
THE FIRST STATEMENT IS TRUE,
AND THE SECOND STEP IS THE INDUCTION STEP
WHERE WE PROVE THAT IF ANY ONE STATEMENT IS TRUE FOR K
THEN THE NEXT ONE, K + 1, IS ALSO TRUE.
LET'S TAKE A LOOK AT AN EXAMPLE.
IF WE LET P SUB N BE THE STATEMENT
WHERE N IS A COUNTING NUMBER,
THEN 1 + 2 + 3 ALL THE WAY TO + N = N(N + 1) DIVIDED BY 2.
SO IF WE WANT TO PROVE THIS STATEMENT
USING INDUCTION THE FIRST STEP, THE BASIS,
IS TO SHOW THAT IT'S TRUE FOR N = 1.
WELL, IF N = 1 WE JUST HAVE 1 ON THE LEFT SIDE,
AND THAT SHOULD EQUAL THIS FORMULA HERE WHEN N = 1.
SO WE HAVE 1(1 + 1) DIVIDED BY 2.
THAT'S GOING TO BE 1(2)/2 WHICH OF COURSE = 1.
SO THE NEXT STEP BECOMES THE INDUCTION STEP, SO FOR STEP TWO,
WE WILL SHOW THAT IF P SUB K IS TRUE
THEN P SUB (K + 1) IS ALSO TRUE.
IF WE CAN PROVE THAT, IT'S GOING TO BE TRUE FOR ALL VALUES OF N,
SO WE WANT TO ASSUME THAT P SUB K,
WHICH WOULD = 1 + 2 + 3 + ALL THE WAY TO K,
WOULD = K(K + 1)/2.
AND AGAIN, WE WANT TO ASSUME THIS IS TRUE.
ALSO NOTICE THAT WE CHANGED THE VARIABLE FROM N TO K,
BUT OTHER THAN THAT IT'S THE SAME STATEMENT.
WE WANT TO SHOW THAT P SUB (K + 1),
WHICH WOULD BE 1 + 2 + 3 ALL THE WAY TO + K + (K + 1),
WOULD = AGAIN, THIS K WOULD BE NOW (K + 1),
AND THEN HERE WE'D HAVE (K + 1) + 1.
I'M GOING TO SHOW THAT THIS IS TRUE.
NOW, IT'S IMPORTANT THAT WE RECOGNIZE WHAT HAPPENED HERE.
NOTICE WHAT WE DID ON THE RIGHT IS WE REPLACED K WITH (K + 1),
SO WHAT WE'RE GOING TO DO NOW IS STARTING WITH P SUB K,
WE'LL ADD (K + 1) TO BOTH SIDES OF THIS STATEMENT HERE AND SHOW
THAT WE CAN TRANSFORM IT INTO THIS STATEMENT HERE.
SO LET'S GO TO THE NEXT SLIDE,
AND WE'RE GOING TO START WITH P SUB K AND ADD (K + 1)
TO BOTH SIDES.
WELL, THERE'S P SUB K, SO P SUB (K + 1) WOULD LOOK LIKE THIS.
AND AGAIN, P SUB K = K(K + 1) DIVIDED BY 2,
AND WE'RE GOING TO ADD (K + 1) TO THIS.
NOTICE HERE IS P SUB K,
AND THEN WE ADDED (K + 1) TO BOTH SIDES OF THE EQUATION.
AND REMEMBER FROM THE PREVIOUS SCREEN,
WE SAID THAT P SUB K + 1,
SO NOW WHAT WE WANT TO DO IS TAKE THIS RIGHT SIDE
AND SEE IF WE CAN REWRITE IT IN THE FORM OF P SUB K + 1
AS WE STATED ON THE PREVIOUS SCREEN.
I WROTE IT DOWN HERE SO WE COULD REFERENCE IT,
BUT AGAIN, THE GOAL IS TO TAKE THIS RIGHT SIDE
AND TRY TO REWRITE IT IN THIS FORM HERE.
AND IF WE CAN DO THAT,
WE WILL HAVE HAVE SHOWN THAT P SUB K + 1 IS TRUE
AND THEREFORE TRUE FOR ALL VALUES OF N.
SO THE FIRST THING WE COULD DO HERE IS REWRITE THIS
WITH A DENOMINATOR OF 2, SO WE CAN THINK OF THIS AS (K + 1)/1
AND THEN MULTIPLY THE TOP AND THE BOTTOM BY 2.
SO IF WE DID THAT, WE WOULD HAVE K(K +1)/2.
THIS WOULD BECOME 2(K + 1)/2.
NOW WE HAVE A COMMON DENOMINATOR,
SO WE CAN GO AHEAD AND ADD THESE TWO FRACTIONS TOGETHER.
SO WE HAVE K(K + 1) + 2(K + 1)/2.
NOW, IF WE TAKE A LOOK AT THIS PRODUCT HERE
AND THIS PRODUCT HERE, THEY HAVE A COMMON FACTOR OF (K + 1),
SO LET'S GO AHEAD AND FACTOR THAT OUT.
FACTOR OUT THE (K + 1).
WE'D BE LEFT WITH (K +2)/2.
AND NOW IF YOU TAKE A LOOK
AT THIS PART OF THE EXPRESSION HERE, WE HAVE (K +1) +1.
THAT'S ACTUALLY (K + 2), AND THAT'S WHAT WE HAVE HERE.
LET'S GO AHEAD AND JUST REWRITE IT IN THIS FORM,
SO IT MATCHES PERFECTLY.
AND THIS DOES = P SUB (K + 1),
SO NOW WE CAN STATE THAT P SUB (K + 1) IS TRUE.
SO WE'RE DONE.
THEREFORE, P SUB K IS TRUE,
AND P SUB (K + 1) IS ALSO TRUE.
SO P SUB N IS TRUE FOR ALL N WHERE N IS A POSITIVE INTEGER.
LET'S SEE IF WE HAVE TIME FOR ANOTHER ONE.
SO FOR THE BASIS, WE WANT TO SHOW IT'S TRUE FOR N = 1.
WELL, IF N = 1 WE WOULD JUST HAVE 3 ON THE LEFT SIDE,
AND THEN N = 1 ON THE RIGHT.
SO WE'D HAVE 3(3 TO THE FIRST - 1) DIVIDED BY 2.
WELL, THIS IS GOING TO BE 3(3 - 1).
THAT WOULD BE 3(2)/2.
WELL, THE 2'S SIMPLIFY OUT, SO WE'RE LEFT WITH 3.
SO FOR THE INDUCTIVE STEP,
WE'RE GOING TO SHOW THAT IF P SUB K IS TRUE
THEN P SUB (K + 1) IS ALSO TRUE.
SO LET'S GO AHEAD AND WRITE OUT P SUB K AND P SUB (K + 1).
P SUB K WOULD BE THE SAME STATEMENT HERE
EXCEPT NOW N IS K, AND P SUB (K + 1) WOULD BE VERY SIMILAR
EXCEPT K IS NOW (K + 1).
SO THIS IS WHERE OUR WORK REALLY BEGINS.
WE WANT TO TAKE P SUB K,
AND THEN WE'RE GOING TO ADD 3
TO THE POWER OF (K +1) TO BOTH SIDES
AND SEE IF WE CAN REWRITE IT IN THIS FORM HERE.
IF WE CAN THEN WE HAVE USED INDUCTION TO PROVE IT'S TRUE
FOR ALL VALUES OF N WHERE N IS A COUNTING NUMBER.
LET'S GO OVER.
TAKE IT TO THE NEXT SLIDE.
STARTING WITH P SUB K, WE'LL ADD 3 TO THE POWER OF (K + 1)
TO BOTH SIDES.
SO WE'LL START WITH P SUB K,
AND NOW WE'RE GOING TO ADD 3 TO THE (K + 1) TO BOTH SIDES.
AND IF WE CAN REWRITE THIS RIGHT SIDE
IN THE FORM OF P SUB (K + 1) AS WE SEE HERE,
WE WILL HAVE SHOWN THAT IT IS TRUE FOR (K +1)
AND THEREFORE ALL VALUES OF N.
SO THIS BECOMES AN ALGEBRA PROBLEM NOW
WHERE WE CAN TRY TO MANIPULATE THIS
TO MAKE IT MATCH THE PREVIOUS FORM.
SO WHAT WE'RE GOING TO DO HERE FIRST IS THINK OF THIS AS OVER 1
AND THEN MULTIPLY BOTH THE TOP AND THE BOTTOM BY 2.
SO WE'D HAVE 3(3 TO THE K - 1)/2 + 2(3 TO THE K +1)/2.
NOW WHAT WE'RE GOING TO DO HERE
IS WE'RE GOING TO ACTUALLY DISTRIBUTE THIS 3
AND THEN COMBINE OVER THE SAME DENOMINATOR.
SO 3(3 TO THE K) WOULD BE 3 TO THE K + 1, THEN WE'D HAVE - 3,
AND THEN WE'D HAVE + 2(3 TO THE K + 1)/2.
REMEMBER, YOU COULD THINK OF THIS AS 1(3 TO THE K +1),
SO 1(3 TO THE K +1) + 2(3 TO THE K + 1)
WOULD GIVE US 3(3 TO THE K + 1) - 3/2.
NOW WE'RE ALMOST THERE.
WE FACTOR OUT THIS 3 IN THE NUMERATOR.
WE HAVE 3(3 TO THE K + 1 - 1)/2.
IF WE GO BACK TO THE PREVIOUS SCREEN,
K SUB (K +1) WAS EQUAL TO THIS,
AND THEREFORE WE HAVE SHOWN THAT IT IS TRUE.
AND LET'S GO BACK AND LOOK AT THAT.
HERE'S THAT FORM WE WERE TRYING TO MATCH,
AND WE DID.
THEREFORE, WE'RE DONE.
SO P SUB (K +1) DOES HOLD,
THEREFORE, P SUB K AND P SUB (K +1) ARE TRUE,
SO P SUB N IS TRUE FOR ALL N WHERE N IS A POSITIVE INTEGER.
AND THAT'S GOING TO DO IT FOR THE INTRODUCTION
TO MATHEMATICAL INDUCTION.
I HOPE YOU FOUND THIS HELPFUL.