7
votes
4answers
272 views

The largest integer less than $n$ is $n-1$

Let $n$ be a positive integer. Prove that the largest integer which is less than $n$ is $n-1$. Attempt of a solution: Since $n$ is a positive integer $n>0$. I think I have to use the well-ordering ...
2
votes
1answer
33 views

is my induction proof sufficient?

question; prove that $\forall\ n\ge4, n\in \mathbb{Z}, \ n!\gt n^2$. my work; let $n=4$ then $4!=24 \gt 4^2=16.$ true. now assume $n! \gt n^2$ is true for all $n\le k$ so now assume $k! \gt ...
3
votes
5answers
578 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 ...
0
votes
1answer
39 views

a finite induction question from burton's elementary number theory

this question comes from burton's elementary number theory, 4th edition. question 3 in 1.1 says to use the second principle of finite induction to establish that $$for\ all\ n\ge1,\ ^{(a)}\ ...
3
votes
2answers
51 views

Proving $\sum_{i=1}^{n}(i)(i!)=(n+1)!-1$ using induction

$\sum_{i=1}^{n}(i)(i!)=(n+1)!-1$ This proposition seem to be true First step $P(1)$ $1=2!-1$ Second step assume $P(k)$ $\sum_{i=1}^{k}(i)(i!)=(k+1)!-1$ Third step $P(k+1)$ The area of ...
2
votes
1answer
44 views

What is the most elementary proof of these inequalities?

Let $p$ be a non-zero integer, and let $x_1$, $\ldots$, $x_n$ be $n$ positive real numbers. Then we define the $p$-th power mean $M_p$ of these numbers as $$ M_p \colon= (\frac{x_1^p + \ldots + ...
0
votes
3answers
77 views

Number Theory - Proof by Induction

Show that: $2903^n - 803^n - 464^n + 261^n$ is divisible by $1897$ for all integers $n\geq1$ using induction.
2
votes
1answer
42 views

Generalized Induction Verification

Consider the following simple exercise. Prove or disprove: $\gcd(km, kn) = k \gcd(m, n)$, where $m, n, k$ are natural numbers. Now, this is easy to prove using prime factorization. Knowing that ...
0
votes
0answers
42 views

Proof by Induction for Fundamental Thm of Arithmetic

Use induction to make our proof of the Fundamental Theorem of Arithmetic more rigorous. Recall that $p$ is prime iff for all $a,b\in\mathbb Z:p\mid(ab)$ implies $p\mid a$ or $p\mid b$. Prove that ...
1
vote
3answers
62 views

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ [duplicate]

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ How would you do the inductive step for this proof? I have the base case done.
0
votes
4answers
50 views

Quick induction proof

I am trying to prove $n^3<n!$ for all integers $n\geq 6.$ It would be trivial to do this by induction if $(n+1)^3<(n+1)n^3$ holds. I looked this up, and I found this is true for integers $n\geq ...
0
votes
1answer
43 views

How to proof this: (m is odd ∧ n is odd)⇒ m + n is even

I don't quite understand why I can not proof the following: Assume that n,m ∈ N. Show: (m is odd ∧ n is odd)⇒ m + n is even. With this: Say n, m are odd. Then the remains of (m + n) / 2 is equal to ...
3
votes
1answer
36 views

$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}$

I'm supopsed to show that if $m$ and $n$ are non-negative integers then $$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}} = \left\{ \begin{array}{l l} 1 & \quad \text{if $n=0$}\\ ...
4
votes
2answers
80 views

$a_1a_2\cdots a_n = 1 \implies a_1 + a_2 + \cdots + a_n \geq n$ if $a_1, a_2, \dots, a_n > 0$

Let $a_1, a_2, \dots, a_n > 0$. I'm trying to prove that if $a_1a_2\cdots a_n = 1$, then $a_1 + a_2 + \cdots + a_n \geq n$ by mathematical induction without using the AM-GM inequality. So far I've ...
0
votes
3answers
59 views

If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

I have been asked to prove the following via induction (as the textbook as suggested): If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$ So, I did the ...
0
votes
1answer
25 views

$lcm(a_{1},…,a_{n})=lcm(lcm(a_{1},…,a_{n-1}),a_{n})$

I tried to prove this by complete induction on $n$ but I am having problems in the inductive step: Suppose $$lcm(a_{1},...,a_{n})=lcm(lcm(a_{1},...,a_{n-1}),a_{n}) \forall k\le n\in \mathbb ...
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 ...
0
votes
2answers
31 views

Induction question help.

Let $x$ and $y$ belong to a commutative ring $R$ with prime characteristic $p$. Show that, for all positive integers $n$ $$ (( x + y )^p)^n = (x^p)^n + (y^p)^n $$ I hope you can can understand ...
0
votes
3answers
37 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
2
votes
0answers
48 views

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

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
17
votes
3answers
712 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 ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
2
votes
1answer
49 views

When is there an $m$ that divides $u^{an+b}+v^{cn+d}$ for all $n$

This is a generalization of Prove by induction? which asks how to prove that $73$ divides $8^{n+2}+9^{2n+1} $for all $n$. Here is my generalization: Find conditions on positive integers $u, a, v, c$ ...
1
vote
1answer
27 views

Is this divisibility proof by induction correct/sufficient?

To show: 13 | $4^{2n+1}+3^{n+2}$ I used induction beginning successfully with n=0 (or n=1), then making the step to n+1: An x exists so that $13x = 4^{2n+3}+3^{n+3}$ $13x = 16*4^{2n+1}+3*3^{n+2}$ ...
2
votes
1answer
75 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}).$$
2
votes
5answers
87 views

Prove by induction that for all $n$, $8$ is a factor of $7^{2n+1} +1$

I want to prove by induction that for all $n$, 8 is a factor of $$7^{2n+1}+1$$ I have proved it true for the base case and assumed it true for $n=k$, but when I cannot figure out when to go towards ...
1
vote
1answer
31 views

I'm not sure if my subscripts are lining up correctly in this elementary number theoretic induction proof

First, the motivation for the below lemma is to use in a proof that every number has a unique representation in a base. My question is that when using the inductive hypothesis, I'm not sure if my ...
3
votes
2answers
108 views

Proving $r!$ divides the product of r succesive positive integers

I have to prove the following theorem: Prove that the product of $r$ consecutive positive integers in divisible by $r!$ I am having a hard time getting a generalization down for the full set of ...
0
votes
2answers
99 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
1
vote
0answers
46 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
2
votes
1answer
119 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
0
votes
4answers
54 views

I've got a small problem with induction

Let me take a quick example: We want to prove by induction that $3^n-1$ is a multiple of 2, where n is a positive integer. So we start with our "base case" and show that $3^1-1$ is indeed a multiple ...
0
votes
1answer
42 views

How Can I find the summation of divisors of $n^p$.

For Example $n=8$ and $p=2$. So $n^p=64$. And the summation of divisors is $1+2+4+8+16+32+64=127$. But the problem arises when $n=10^6$ and $p=10^6$. Remember u can modulus the result by $100$.
2
votes
4answers
111 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
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 ...
2
votes
1answer
42 views

Let $a_n=2^{2n}\left(2^{2n+1}-1 \right)$. Show induction of $n$

Let $a_n=2^{2n}\left(2^{2n+1}-1 \right)$. Show induction of $n$ $$a_{2n+1}=256a_{2n-1}+60\left(16^n\right)$$ $$a_{2n+2}=256a_{2n}+240\left(16^n\right)$$ I tried $n=1$, ...
7
votes
10answers
1k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
2
votes
1answer
282 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.: ...
1
vote
5answers
66 views

$(x - 1)|(x^n -1); \forall x \neq 1 $ by induction.

I am just hoping to get some help on this question. Show that: $$\forall x \neq 1; (x - 1)|(x^n -1)$$ I am trying to prove this by induction on $n$. Here is what I have so far: $ \forall x \neq 1; ...
1
vote
1answer
198 views

Frobenius coin problem, 5 and 9

I am hoping to get some help with two problems related to Forbenius coin problems. A) A fictional government has decided to issue currency in only 5 and 9 value denominations. Prove that there is a ...
1
vote
3answers
76 views

Prove by induction that $3\mid (n^3 - n)$

I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure it's correct. My answer: Proof by induction: ...
2
votes
2answers
55 views

Demonstration that $\forall\; n>3,\;\;n^2<n!$

How do I prove by mathematical induction that$$\forall\; n>3,\;\;n^2<n!$$ I tried, $n=4$ then $4^2<4!$ what is true, because $16<24$.$$$$Hypotesis: $n^2<n!$ $$$$Thesis: ...
3
votes
4answers
159 views

How can I show that $4^{2n}-1$ is divisible by $15 $ for all $n$ greater or equal to $1$

Ok so this is a question from a book that has no included solution and I think I'm on the right way but I just need a little help. The question is: Show, for all $n \ge 1$ such that $4^{2n} - 1$ ...
0
votes
2answers
113 views

fill-in-the-blank induction proof

I'm stuck at homework task I'm working on. I would really appreciate some help. Here is the task: Let $f$ be a function on binary numbers defined recursively as follows. $f(0) = 1$ and ...
6
votes
5answers
302 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 ...
2
votes
1answer
58 views

Induction and Countable Set

Ok well everytime ive seen induction being used, its been on the naturals for a statement we wish to prove. My question is would any countable set also work? Hence, doing induction on the rationals as ...
1
vote
3answers
150 views

Prove some divisibility results by induction

Please hint me, I have two questions: Prove by induction that: 1) $$ {13}^n+7^n+19^n=39k,\,\, n\in\mathbb O$$ in which $\mathbb O$ is the set of odd natural numbers. 2) $$ ...
2
votes
5answers
108 views

Given $n \in \mathbb{N}$ prove that a polynomial result gives a natural number.

A friend asked me this question: Prove that for every $n\in \Bbb N$ the next equation result: $\dfrac{n^3}{6}+\dfrac{n^2} {2}+\dfrac{n}{3}$ would be a natural number. My instincts were that i need ...
1
vote
0answers
43 views

Show by induction… Help

Let $a,n\in\mathbb{N}$, show that there exists $m\in\mathbb{N}$, such that $(a+1)^n=ma+1$ I tried to do by induction on $n$, but found it a bit strange the demonstration. ...