# Questions tagged [induction]

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the base case, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant for questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

9,773 questions
Filter by
Sorted by
Tagged with
36 views

### How to prove $1^3+5^3+3^3=153,16^3+50^3+33^3=165033,166^3+500^3+333^3=166500333,\cdots$ with mathematical induction?

$1^3+5^3+3^3=153$ $16^3+50^3+33^3=165033$ $166^3+500^3+333^3=166500333$ $1666^3+5000^3+3333^3=166650003333$ $...$ People in the below link proves the above identities. The proof without mathematical ...
37 views

### Can one prove a continuous inequality by "induction"? [duplicate]

I want to prove an inequality of the following form: $$f(x) \le g(x) \quad \forall x \ge 0.$$ In my case, $f(0) = g(0)$ I am wondering if the following would be a viable method. Is the inequality ...
• 3
49 views

### Prove using induction over the positive integers

Prove using induction that the sum of the first step $n$ positive even integers is $n(n+1)$. In other words, prove using induction that $2 + 4 + 6 + … + 2n = n(n+1)$. So, for my base case I have: the ...
66 views

### Prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$ [duplicate]

How to prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$, with $n,m$ positive integers? I have tried by induction (on $n$) and with the binomial theorem, something like this (have also assumed $m$ ...
• 9
35 views

### What does it mean that we need $𝜖_0$ induction to prove PA consistency?

I have started to learn about Peano Arithmetic, and also about ordinals. In particular, I have seen that the Goodstein theorem is an example of a statement that can be expressed in PA but that ...
• 389
35 views

46 views

### An exercise from Shapiro's Abstract Algebra [duplicate]

Ex. 8 of the first chapter. The statement is as follows. This exercise is higly recommended if you want or need to practice induction proofs. We define $a^2$ as $a*a$, $a^3$ as $a*a*a$, and for $n$ a ...
• 573
1 vote
38 views

### Prove that exists Gray Codes of length $\lceil \log_2 k \rceil$ for any positive integer $k$

Prove that exists Gray Codes of length $\lceil \log_2 k \rceil$ for any positive integer $k$. The Gray codes for even $k$ values are closed (form a unique cycle), the ones for odd $k$ values are open. ...
53 views

### Stuck on mathematical induction proof at inductive step [duplicate]

Here's the problem: Use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of 5. This is what I have so far: Basis: $n= 1$, $n^5-n = 1-1 = 0 = (5)(0)$ so $1^5 - 1$ is ...
82 views

### Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$

Let $p,q\in\mathbb N$. Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$. Things I already proved and might help: $p^2\neq2$ if $(\frac{p}{q})^2=2$ ...
• 25
861 views

### Existential crisis about proof by induction

I recently read this post on this website and it gave me a bit of an existential crisis about proof by induction. My understanding is that, in proof by induction, we show two things to be true: $P(0)$ ...
74 views

### Prove the product of 3 consecutive positive integers is always divisible by 6 via induction [duplicate]

There is a problem asking me to prove the product of 3 consecutive integers is always divisible by 6 by using induction and not using the fact that one of the 3 numbers must always be divisible by 3. ...
72 views

### Confusion in a proof that there is no $n$ such that $1<n<2$?

I am trying to follow a proof in Hijab's: Introduction to Calculus and Analysis. He gives the definition of inductive set: And then there is this proof where he shows that there is no $n$ between $1$ ...
• 23.1k
91 views

### Inequality for triple product of Stirling numbers

Let ${n\brace k}$ be the Strirling number of the second kind, such that ${n+1\brace k} =k{n\brace k}+{n\brace k-1}$ with ${0\brace 0}=1$. Let $j,p,n$ integers such that $1 \le j \le p \le n$. I ...
• 3,611
71 views

### Is my proof by mathematical induction that $n(n+2)$ is divisble by 4 correct?

Problem: Prove that $n(n+2)$ is divisible by $4$ by using mathematical induction, if $n$ is any even positive integer. My attempt: $P(q):$ "$2q(2q+2)$ is divisible by $4$", where $q$ is a ...
• 2,923
1 vote
62 views

### Prove using mathematical induction that $1 \cdot 2 + 2\cdot3+ ...+n(n+1) = \frac{n(n+1)(n+2)}{3}$ [duplicate]

I need to prove that for any n ∈ $\mathbb{N}$, $\begin{equation}\label{eqn1}1 \cdot 2 + 2\cdot3+ ...+n(n+1) = \frac{n(n+1)(n+2)}{3}\end{equation}$ (1). So, this is what I've done so far: BASIS STEP: ...
• 53
72 views

### Equivalent inductive step to $P(n) \implies P(n+1)$

In a usual proof by induction the inductive step involves assuming $P(n)$ is true and then showing that $P(n+1)$ follows. Are there any other valid inductive steps? That is, can we define an ...
1 vote
67 views

432 views

### Mathematical induction proof for integers

Use mathematical induction to prove that $n! > 4^n$ for $n \geq 9$. My attempt: Base case: For $n=9$, we have $9! = 362880$ and $4^9 = 262144$ Since $9! > 4^9$, the statement is true for $n=9$ ...
87 views

### Prove the recurrence relation $T(n) = 2T(n/2) + n$ is equal to $n\log(n) + n$ using induction

Question Given the recurrence relation for the Merge Sort algorithm: $T(n) = 1$, if $n = 1$ $T(n) = 2T(n/2) + n$, if $n > 1$ Prove by induction that $T(n) = n\log(n) + n$ and hence $O(n\log(n))$ My ...
54 views

### On a rather strange induction [duplicate]

I've been studying elementary number theory for a while now, and when it's possible, to wit somewhat elegant, I love using induction. I was solving the following problem: "if m$\phi$(m) = n$\phi$(...
• 7
157 views

### Given $a_1$, find an increasing sequence so that $a_1+\dots+a_k$ divides $a_1^2+\dots+a_k^2$ for all $k$

Prove that for every natural number $a_1>1$ there's an infinite series $a_1<a_2<a_3<...$ such that for every natural number $k,$ $a_1+a_2+...+a_k \vert a_1^2+a_2^2+...+a_k^2$. At first ...
• 417
1 vote