3
votes
5answers
576 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
1
vote
3answers
71 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
1
vote
2answers
30 views

$3^a\mid s(n) \Rightarrow 3^a\mid n$

This is not a homework question, neither a championship problem (as far as I've searched in the net), and it came up noticing a singular pattern, involving the powers of $3$: "Prove or disprove that ...
3
votes
3answers
233 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
6
votes
0answers
67 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
17
votes
3answers
710 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
2
votes
1answer
74 views

Proving divisibility by using induction: $133 \mid (11^{n+2} + 12^{2n+1})$ [duplicate]

If $n > 0$, then prove the following by using induction: $$133|(11^{n+2} + 12^{2n+1}).$$
1
vote
3answers
91 views

Proof that $23^{n} - 1$ is divisible by $11$ for all positive integers $n$.

I'm having a bit of a problem proving this statement. Maybe someone can point me in the right direction? Best regards,
1
vote
6answers
147 views

Prove that ${n^5 - n}$ is divisible by 5 [duplicate]

I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it. I am trying to prove it for several hours now, I started with ${n^5 - n} \mod 5 = 0$ but then I ...
3
votes
2answers
72 views

Prove by induction $a-b|a^{n}-b^{n}$ for $n\in\mathbb N$

$P(1)$: $a-b|a-b$ $P(n) \Rightarrow P(n+1)$: $a-b|a^{n}-b^{n}\Rightarrow a-b|a^{n+1}-b^{n+1}$ I'm not sure how to proceed from here. Any help is appreciated.
1
vote
3answers
49 views

Prove by induction that $99 | 10^{2n} + 197$ for $n\ge 1$

I'm not sure whether I should make use of the transitive property, or this $a|b\Rightarrow b = a*z$ / $z\in\mathbb Z$ to solve the problem. I'm mainly looking to solve it through induction using the ...
0
votes
2answers
48 views

Legality of doubly inductive proof requiring two base cases

I aim to show that the proposition $P_n$: "$11^n - 4^n$ is divisible by $7$" is true for all $n\in\mathbb{N}$. Assume that for some $n \ge 2$, $P_n$ is true. Then since \begin{align} 11^{n+1} - ...
1
vote
1answer
75 views

prove by induction that $n(n+1)(n+2)(n+3)$ is an integer multiple of $24$

prove by induction that $n(n+1)(n+2)(n+3)$ is an integer multiple of $24$ Let $P(n)$ be the proposition we want to prov, ie: $P(n):=24 \mid(n)(n+1)(n+2)(n+3)$ For $P(1)$ we have: $24 ...
2
votes
2answers
66 views

Divisibility Of Positve Integers [closed]

Suppose a,b and c are three positive integers which satisfy the condition that ($a$2+$b$2+$c$2) is divisible by $(a+b+c)$. Prove that there exists infinitely many positive integers $n$ for which ...
0
votes
1answer
47 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
-1
votes
2answers
53 views

For any integer $n\ge0$ it follows that $9\mathrel|(4^{3n}+8)$?

I have been trying to use induction in order to prove the above statement but I always reach a dead end. How can this statement proven via induction? Thank you!
-1
votes
1answer
47 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
0
votes
0answers
42 views

Proof that $ k^2<2^k$ [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $k\geq 5$, prove that $k^2<2^k$. I assumed that $k^2<2^k$ I want to show that $(k+1)^2<2^{k+1}$ The ...
2
votes
6answers
124 views

Proof that $n^3-n$ is a multiple of $3$. [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $n$, prove that $n^3-n$ is a multiple of $3$. I assumed that $k^3-k=3r$ I want to ...
2
votes
1answer
280 views

Prove by induction that $a-b|a^n-b^n$ [duplicate]

Given $a,b,n \in \mathbb N$, prove that $a-b|a^n-b^n$. I think about induction. The assertion is obviously true for $n=1$. If I assume that assertive is true for a given $k \in \mathbb N$, i.e.: ...
0
votes
3answers
263 views

Prove $x^n-1$ is divisible by $x-1$ by induction

Prove that for all natural number $x$ and $n$, $x^n - 1$ is divisible by $x-1$. So here's my thoughts: it is true for $n=1$, then I want to prove that it is also true for $n-1$ then I use long ...
6
votes
5answers
301 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
0
votes
4answers
107 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
3
votes
3answers
686 views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
6
votes
1answer
716 views

Proof by induction on Fibonacci numbers: show that $f_n\mid f_{2n}$

I was studying Mathematical Induction when I came across the following problem: The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation- $f_n = f_{n-1} + ...
2
votes
7answers
254 views

Prove that $9\mid (4^n+15n-1)$ for all $n\in\mathbb N$

First of all I would like to thank you for all the help you've given me so far. Once again, I'm having some issues with a typical exam problem about divisibility. The problem says that: Prove ...
4
votes
3answers
298 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
1
vote
2answers
815 views

Understanding mathematical induction for divisibility

I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it ...
19
votes
5answers
3k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
2
votes
3answers
116 views

Proving that an expression divides a number

How do you prove that $$n(n+1)(n+2)$$ is divisible by 6 by using the method of mathematical induction? According to my book $$\begin{aligned} (n+1)(n+2)(n+3) &= n(n+1)(n+2)+3(n+1)(n+2)\\ &= ...
8
votes
6answers
2k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
-2
votes
3answers
1k views

Induction principle for verifying divisibility

I am stuck on one question: Show that $8^n-3^n$ is divisible by $5$. Thank you
1
vote
2answers
159 views

Prove that $2^n | P(2n, n)$

I am attempting to use Induction to prove this, but I am not sure if it is the right method to take. Here is what I have tried: Induction Hypothesis: Assume $P(k)$ is true for some fixed $ k \geq 1$ ...
3
votes
3answers
676 views

Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n $. I want to prove that $P(n)$ is true for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the inductive step, I ...
3
votes
1answer
156 views

Good resource of maths problems with solutions

I'm searching for a good book or web page that has a good amount of problems and their solutions, at undergraduate level, of divisibility, inequalities, induction, etc. Thanks in advance