Proof by mathematical induction

In summary, the conversation is about proving by mathematical induction that for all positive integers n, the expression 10^{3n}+13^{n+1} is divisible by 7. The individual discussing the problem is stuck at a certain step and is seeking help. The solution is to rewrite the constants in terms of 7 and then expand the equation to see how it can be manipulated into the initial inductive hypothesis. The general advice given is to always try to rewrite unwanted constants in terms of the number being divided by.
  • #1
rock.freak667
Homework Helper
6,223
31
[SOLVED] Proof by mathematical induction

Homework Statement


Prove by mathematical induction that for all +ve integers n,[itex]10^{3n}+13^{n+1}[/itex] is divisible by 7.


Homework Equations





The Attempt at a Solution



Assume true for n=N.
[tex]10^{3N}+13^{N+1}=7A[/tex]

Multiply both sides by ([itex]10^3+13[/itex])

[tex](10^{3N}+13^{N+1})(10^3+13)=7A(10^3+13)[/tex]

[tex]10^{3N+3}+ 10^3(13^{N+1})+13(10^{3N})+13^{N+2}=7A(1013)[/tex]

[tex]10^{3N+3}+13^{N+2}=7A(1013)-10^3(13^{N+1})-13(10^{3N})[/tex]

Here is where I am stuck. I need to show that [itex]10^3(13^{N+1})-13(10^{3N})[/itex] is divisible by 7 now.

What I would like to get is that [itex]10^3(13^{N+1})-13(10^{3N})[/itex] can somehow be manipulated into the initial inductive hypothesis and then it will become true for n=N+1. So I need some help.
 
Physics news on Phys.org
  • #2
the standard trick here is to write the 10^3 and the 13 in terms of multiples of 7, plus or minus 1
 
  • #3
Uhm...I can write 13 as 2(7)-1 and 10^3 as 143(7)+1 but I don't see how that helps.
 
  • #4
well then if you expand things out you should see what happens to the equation
 
  • #5
ah..thank you scottie_000

I see it now, was so simple.So when I have to prove that some expression is divisible by a number,k, always try to rewrite any unwanted constants in terms of k?
 
  • #6
like i said, it's the best trick to look for
glad to help by the way!
 

Related to Proof by mathematical induction

What is mathematical induction?

Mathematical induction is a method of mathematical proof used to prove statements about all natural numbers. It involves proving a base case, typically n=1, and then showing that if the statement holds for some arbitrary natural number k, it also holds for k+1. This ensures that the statement holds for all natural numbers.

Why is mathematical induction useful?

Mathematical induction is useful because it allows us to prove statements about infinitely many natural numbers without having to explicitly check each one. It is also a powerful tool in computer science, where it is used to prove the correctness of algorithms and data structures.

What are the steps for a proof by mathematical induction?

The steps for a proof by mathematical induction are as follows:

  • Step 1: Prove the base case, typically n=1.
  • Step 2: Assume the statement holds for some arbitrary natural number k.
  • Step 3: Use the assumption to prove that the statement also holds for k+1.
  • Step 4: Conclude that the statement holds for all natural numbers by the principle of mathematical induction.

What is the principle of mathematical induction?

The principle of mathematical induction states that if a statement is true for the base case and if the truth of the statement for one natural number implies the truth of the statement for the next natural number, then the statement is true for all natural numbers. This forms the foundation of the proof by mathematical induction.

What types of statements can be proved using mathematical induction?

Mathematical induction can be used to prove statements about any mathematical object that can be indexed by the natural numbers, such as integers, rationals, polynomials, and sequences. It is also commonly used to prove properties of mathematical functions and algorithms.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
890
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • General Math
Replies
8
Views
2K
  • Topology and Analysis
2
Replies
48
Views
3K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
10
Views
129
  • Introductory Physics Homework Help
Replies
2
Views
918
Back
Top