Proving Divisibility by Induction

In summary, the conversation discusses two proofs by induction. The first one, for problem #12, involves proving that for all positive integers n, 3 divides 4^n + 5. The base case is P(1) = 3, and the trick is to factor out a 4 and add 0 in a creative way so that the sum of two numbers is divisible by 3. The second proof, for problem #17, involves proving two statements about the number An defined by a recursive formula. The statements are that An is always greater than 0 and less than 5. The conversation includes some calculations and thoughts on how to approach the proofs, but no concrete solutions are given.
  • #1
Jamin2112
986
12
Here are some that I'm stuck on.

Pg. 56, #12

Prove by induction on n that, for all positive integers n, 3 divides 4^n + 5

Of course, the base case it is P(1) = (4^1 + 5) / 3 = 9/3 = 3...TRUE!

I just can't see the trick here. P(K+1)= (4^(K+1) + 5) / 3 = ((4)(4^K) + 5)/3= ... not getting anywhere, really.

Pg. 55, #17

For a positive integer n the number An is defined by
A1=1 [supposed to A with a subscript 1]
Ak+1 [supposed to A with a subscript k+1] = (6Ak+5)/(Ak+2)

Prove by induction on n that, for all positive integers (i) An>0 and (ii) An<5

I see by long division that we have
Ak+1=1-7/(Ak+2)... not sure if that helps. I know that Ak+1 will be zero with Ak=5...no sure if that helps though...
 
Physics news on Phys.org
  • #2
#12) Consider adding 0 in a creative way...so that you can factor out a 4 completely and have the sum of two numbers that are both divisible by 3.
 

FAQ: Proving Divisibility by Induction

What is induction in mathematics?

Induction is a mathematical proof technique used to prove that a statement is true for all natural numbers. It involves showing that the statement is true for a base case, typically n=1, and then showing that if the statement is true for some arbitrary number k, it must also be true for k+1.

Why is induction used as a proof technique?

Induction is used as a proof technique because it allows us to prove that a statement is true for an infinite number of cases without having to verify each one individually. It is a powerful and efficient way to prove mathematical statements.

How is induction different from deduction?

Deduction is a logical process that uses a set of premises to arrive at a conclusion. Induction, on the other hand, uses specific examples to prove a general statement. In deduction, the conclusion is guaranteed to be true if the premises are true, whereas in induction, the conclusion is only likely to be true based on the examples shown.

What is the importance of the base case in an induction proof?

The base case is the starting point of an induction proof. It is crucial because it establishes that the statement is true for at least one value of n. Without a valid base case, the proof would not be valid for any value of n.

Can induction be used to prove any mathematical statement?

No, induction can only be used to prove statements that are true for all natural numbers. It cannot be used for statements involving real or complex numbers, as they are not discrete and countable like natural numbers.

Similar threads

Prove this problem that involves Mathematical induction
Replies
8
Views
1K
Proofs By Induction: Proving P(n) for All n
Replies
3
Views
2K
[L'Hospital's Rule] Can I Use Mathematical Induction to Prove This?
Replies
6
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
Replies
5
Views
2K
Induction Proof, Apostol Calc Vol I, I.4.4.7
Replies
6
Views
2K
Show that k is an odd integer, except when k=2
Replies
9
Views
2K
If p##\geq##5 is a prime number, show that p^{2}+2 is composite?
Replies
3
Views
1K
If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....
Replies
15
Views
3K
Find the roots of the complex number ##(-1+i)^\frac {1}{3}##
Replies
22
Views
2K
Determine whether the integer 701 is prime by testing?
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top