induction – Mathemafrica

Prove that for every positive integer n, 9^n – 8n -1 is divisible by 64.

Prove that for every positive integer \(n\), \(9^n-8n-1\) is divisible by 64.

This question screams proof by induction, so we start with the base case, which in this case is \(n=1\):

\(9^1-8-1\) which is indeed divisible by 64.

Now, let’s assume that it holds true for some positive integer \(n=k\). ie:

\(9^k-8k-1=64p\) for \(p\in\mathbb{Z}\).

Now let’s see how we can use this to prove that the statement holds true for \(n=k+1\). For \(n=k+1\) we have:

\[9^(k+1)-8(k+1)-1=9(9^k)-8k-8-1=9(9^k-8k-1)+64k\]

where we have manipulated the expression to contain the left hand side of the inductive hypothesis. Thereby, plugging in the inductive hypothesis, we get:

\[9^(k+1)-8(k+1)-1=9(9^k)-8k-8-1=9(64p)+64k=64(9p+k)\]

but clearly \(9p+k\) is an integer, so this is divisible by 64 and thus the statement holds true for \(n=k+1\), thus it holds true for all positive integers \(k\)

How clear is this post?

…

By Jonathan Shock| October 24th, 2018|Courses, First year, MAM1000, Uncategorized, Undergraduate|0 Comments

Mathematical induction with an inequality

In the tutorial sessions it was clear that one question in particular was causing problems. This is an induction proof with an inequality. The one which we will look at is the inequality:

\(2^n>n^3\) for \(n\ge 10\)

I am going to talk you through it in more detail than would be needed for the formal proof but I want to give some intuition along the way.

So, we start off, as always with the base case. The base case is always the first integer for which the statement is claimed to be true. In this case it is for n=10. Let’s check for n=10. Is it true that?

\(2^{10}>10^3\) ?

Well this is:

\[1024>1000\]

and so we should be happy with that. We’ve proved the base case. Note that you do not then need to check for n=11, or n=12. I have seen many students check a base case for n=1, and then also check for n=2 and n=3.…

By Jonathan Shock| March 9th, 2016|Courses, First year, MAM1000, Undergraduate|11 Comments

Mathematical induction

One of the concepts that most students seem to struggle with the most in the first year maths course is that of mathematical induction. It feels abstract, yet when you have to prove a concrete statement, it feels like all the assumptions, and cases you look at shouldn’t have any real impact on the thing that you’re trying to prove. I will now try and prove that this is not true (though not by mathematical induction!).

I’m going to start with a ladder brought from a magical ladder supplier. Steps on the ladder are labeled S(1), S(2), S(3) etc. The question is, are there infinitely many steps on the ladder? Well, with the information that I’ve given you so far, you just don’t know, but the manufacturer has given a little leaflet with the it. In the leaflet it says:

“As long as your ladder has a step S(n), we hereby guarantee that it will have a step S(n+1), for any integers n”.…

By Jonathan Shock| March 6th, 2016|Courses, First year, MAM1000, Undergraduate|6 Comments

Fibonacci and induction

The Fibonacci numbers \(F_n\) are defined by: \(F_1 = F_2 = 1\), \(F_{n+2} = F_{n+1} + F_n \textrm{ for } n\ge 1.\)

The numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

The Fibonacci numbers have many interesting properties, and the proofs of these properties provide excellent examples of Proof by Mathematical Induction. Here are two examples. The first is quite easy, while the second is more challenging.

Theorem

Every fifth Fibonacci number is divisible by 5.

Proof

We note first that \(F_5 = 5\) is certainly divisible by 5, as are \(F_{10} = 55\) and \(F_{15} = 610.\) How can we be sure that the pattern continues?

We shall show that: IF the statement “\(F_n\) is divisible by 5″ is true for some natural number \(m\), THEN the statement is also true for the natural number \(m+5\).

Now

\[F_{m+5} = F_{m+4} + F_{m+3}\]

\[= (F_{m+3} + F_{m+2}) + F_{m+3}\]

\[= 2F_{m+3} + F_{m+2}\]

\[= 2(F_{m+2} + F_{m+1}) + (F_{m+1} + F_m)\]

\[= 2F_{m+2} + 3F_{m+1} + F_m\]

\[= 2(F_{m+1} + F_m) +3F_{m+1} + F_m\]

\(= 5F_{m+1} + 3F_m\).

Since we know that \(F_m\) is divisible by 5, it is now clear that \(F_{m+5}\) is also divisible by 5.…

By Jonathan Shock| October 18th, 2015|English, Level: intermediate|3 Comments