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.

Filter by
Sorted by
Tagged with
0
votes
0answers
9 views

Induction to Define Permutation (Propositional Logic)?

For a well-formed formula φ, use induction to define permutation(φ), which is the number of logically equivalent formulas obtained from φ by changing the order of the operands in the logical ...
0
votes
1answer
26 views

Probability of the product of i.i.d. r.v. with values in $\{-1, 1\}$ is equal to the probability of any member of the product equaling the product

Let $(C_k)_{k=1}^\infty$ be a sequence of i.i.d. r.v. with values in $\{-1, 1\}$ by distribution $\mathbb{P}(C_k = 1) = 0.5 = \mathbb{P}(C_k = -1), \forall k$. I'd like to express that the probability ...
0
votes
0answers
39 views

Prove that the sequence is correct

Let $(x_n)_{n \in \mathbb{N}}$ be a sequence such that $x_1 = 8$, $x_2 = 13$ and $$x_n = 7x_{n-1} - 6x_{n-2} \qquad \forall n \geq 3\,.$$ I am trying to prove that $$\forall n \in \mathbb{N} \; (x_{n}=...
0
votes
1answer
35 views

Induction: If $A, B_{1}, B_{2}, \ldots, B_{n}$ are any sets, then $\forall n \geqslant 2$.

I have an induction homework. Is my result correct? I think I've just overthinking in this problem. Am I on the right track or is my conclusion correct? Thank you. Use weak induction to show that if $...
2
votes
1answer
50 views

Prove $\sum_{k=1}^n \frac{1}{k(k+1)} = 1 - \frac{1}{n+1}$ by induction

I'm not sure if my induction proof is correct. If anyone could kindly review it, I'd appreciate it. Prove that $n \in \mathbb{N}$: $\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+\dotsm+\frac{1}...
-4
votes
1answer
36 views

How to prove using mathematical induction that $25\mid2^{n+1}\cdot 3^n + 30n -4$? [closed]

How to prove using mathematical induction that $25\mid 2^{n+1}\cdot3^n +30n -4$?
1
vote
1answer
54 views

How to transform a union of intervals into a disjoint union of intervals

Let $([a_i,b_i])_{1\leq i\leq n}$ be a family of closed intervals of $\mathbb{R}$. I want to prove that there exists a family of disjoint intervals $([c_i,d_i])_{1\leq i\leq m}$ for $m\leq n$ such ...
2
votes
1answer
79 views

If a wff is longer then the sum occurrences of atoms and connectives is bigger.

Let $\#(\phi)$ denote the sum of (not necessarily distinct) occurrences of atoms and connectives of the wff $\phi$.Let $l(\phi)$ denote length of the wff $\phi$. Is it true that for all wff's $\phi$ ...
2
votes
0answers
31 views

Applying mathematical induction to a statement involving two integers

$ \newcommand{\N}{\mathbb{N}} $ Let $R$ be a transitive binary relation on $X$ and $(x_n)_{n\in\N}$ be a sequence in $X$. Claim: If $\forall n \in \N: x_n R x_{n+1}$, $$ \forall m, n \in \N: [m < n ...
1
vote
1answer
84 views

I can't prove $U_{n} \geq 1$

So we have an iteration: $U_{n+1} = 1 + \frac{1}{U_{n}+1}$ where $n$ is a natural number and $U_{0} = 1$ I have to prove $U_{n} \geq 1$ but the problem is that I just can't. Here is my attempts: By ...
1
vote
1answer
91 views

Is my (first) proof by induction correct?

I am self-studying and would very much appreciate some feedback on my first ever induction proof. Let $y_1 = 6$, and for each $n\in \mathbb{N}$ define $y_{n+1} = (2y_n - 6)/3$. Use induction to prove ...
0
votes
1answer
29 views

I need help with this induction proof

I need help prooving this with induction for n greater or equal to 2. I know what induction is and how it works but I'm having a hard time with this one. I know $ \prod_{k=1}^{n+1} = (\prod_{k=1}^{n}...
0
votes
2answers
75 views

Show that $\frac{1}{2^2}+\frac{1}{3^2}+\text{...}+\frac{1}{n^2}<1$ [duplicate]

Show that $$\dfrac{1}{2^2}+\dfrac{1}{3^2}+\text{...}+\dfrac{1}{n^2}<1$$ for all $n\ge2,n\in N.$ Initially, we should prove the proposition is true for $n=2$. $$\dfrac{1}{2^2}\overset{?}{<}1\\\...
1
vote
2answers
80 views

Inductive definition of a function in a formal language

$ \newcommand{\emt}{\varnothing} \newcommand{\N}{\mathbb{N}} \newcommand{\dom}{\mathrm{dom}} $ My new formal proof is updated at the end of the post: I am trying to show the following proposition: Let ...
3
votes
1answer
69 views

How to Use Math Induction to prove my formula?

On day one, I was fined 2 dollars. Every subsequent day the fine is squared (i.e., day 1: 2, day 2: 4, day 3: 16, day 4: 256, day 5: 65,536). After some analysis, I came up with the formula to ...
0
votes
1answer
71 views

Show that $1+\frac12+\frac13+\text{...}+\frac{1}{2n-2}+\frac{1}{2n-1}<n$

Show that $$1+\dfrac12+\dfrac13+\text{...}+\dfrac{1}{2n-2}+\dfrac{1}{2n-1}<n$$ for all $n>1,n\in N.$ Initially, we should prove the proposition is true for $n=2$. I wasn't sure how the LHS was ...
1
vote
2answers
152 views

Can this Minimization Problem be Proved through Induction?

Consider the following function (this function has $n$ dimensions): $f(x_1,...,x_n)=10n+\sum_{i=1}^n(x_i^2-10\cos(2\pi x_i));\quad -5.12\leq x_i\leq 5.12$, $\text{minimum at }f(0,...,0)=0$. Using ...
-1
votes
2answers
98 views

Show that $1^3+2^3+3^3+\text{...}+n^3=(1+2+3+\text{...}+n)^2$ [duplicate]

Show that $$1^3+2^3+3^3+\text{...}+n^3=(1+2+3+\text{...}+n)^2$$ For $n=1$ we have $$1^3=1^2$$ which is obviously true. Assume that $$1^3+2^3+3^3+\text{...}+k^3=(1+2+3+\text{...}+k)^2$$is true for some ...
1
vote
1answer
48 views

How can I use "proof by contradiction" in an induction proof?

I am wondering how I can show the second statement as a proof by contradiction: Do I have something like $(\begin{align}\forall n\geq n_{0}:A(n)\implies A(n+1)\end{align})\iff(\forall n\geq n_{0}:A(n)...
0
votes
2answers
64 views

When proving divisibility by induction, how does $f(k+1) - f(k)$ help us to prove it? [closed]

I was going through my textbook and I found that when you're proving divisibility for a function $f(n)$, one approach is to use $f(k+1) - f(k)$ but it doesn't explain why it works. I haven't been able ...
5
votes
2answers
71 views

Prove $n + H(1) + H(2) + H(3) + ... + H(n-1) = nH(n)$ by induction

The question below is an extension question from an exercise booklet and I am unable to complete a small part of this problem at the end. I seem to be stuck on simplifying the left hand side during ...
0
votes
0answers
45 views

Let $n\ge2$ and $a_1,a_2,\dots,a_n$ be positive reals such that $a_1a_2\dots a_n=1$. Use mathematical induction to prove that $a_1+a_2+\dots+a_n\ge n$

I'll start by explaining my approach: First I start by proving the base step ($n=2$) I get a quadratic equation, after solving for its range, I'm able to solve the base step. For the latter part, I ...
1
vote
1answer
84 views

How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?

I have been asked this question in an assignment for my exam. The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
0
votes
0answers
17 views

Doubt on the second step of the induction principle

I have a doubt about the induction principle. Let's prove that $p(n)$ is true $\forall n\geq n_0$. The first step consists in verifying that: $p(n_0)$ is true. The inductive step consists in supposing ...
0
votes
0answers
33 views

How to equalize the right and left hand side of this equation in induction

so im currently doing an induction problem, and I'm at the stage where I have to prove the K+1, but I'm stuck on how to equalize the left and right hand side of this equation. can anyone help me with ...
0
votes
1answer
61 views

Was the effective coverage of induction really just natural number?

If we look up the definition of induction, that is by showing the base case and statement n => n +1 then we would get ever single natural number proofed for what ever we desire, more over , this ...
1
vote
0answers
151 views

does induction work for complex numbers?

im working on an simple question as: Using induction, prove that for all complex numbers a and b and for all natural numbers $m$ and $n$, we have $(ab)^n = a^n \cdot b^n $and also $(a^m )^n = a^{mn}$ ...
0
votes
1answer
74 views

Prove with induction: $\forall n \in \mathbb{N}_{>2} \: \exists y\in \mathbb{N}: (n+2)^3 + 2(n+2) = 3y$

I need help to show this proof by induction: $\forall n \in \mathbb{N}_{>2} \: \exists y\in \mathbb{N}: (n+2)^3 + 2(n+2) = 3y$ So far I have "transformed" the universial quantor to a sum ...
0
votes
2answers
124 views

Proof $\forall n\in\mathbb{N}$, that $9|10^n-1$ by mathematical induction

I think I proved this but I am not to confident in my proof. I am also not that good at formating my proofs so any feedback would be appreciated :) Let $P(n)=9|10^n-1$ Base Case: $9|10^1-1\implies9|9\...
1
vote
0answers
75 views

$f: \mathbb{N} \to \mathbb{N}$, Find $f$ with Mathematical Induction of the value of $f(x)-f(x-1).$

$ f:\mathbb{N}\to\mathbb{N}. \\ \ \\\text{i)} \ \ \ \ f(x-1)f(x+1)=\big(f(x)\big)^2 \text{ for } \forall x \in \mathbb{N} \text{ s.t. } \frac x 2 \in \mathbb{N}. \\ \text{ii)} \; \; f(x-1)+f(x+1)=2f(x)...
6
votes
1answer
127 views

Prove that $\sin nx\le n\sin x$, by Induction

I have to prove that $\sin nx\le n\sin x,\ \forall n\in\mathbb{N},\ 0\le x\le \pi/2$, using Mathematical Induction. The problem arises during the inductive step. What I've done so far, is $$\sin(k+1)x=...
0
votes
2answers
124 views

Prove that $\frac{1}{2} + \sum_{k=1}^n\cos(kx) = \frac{\sin(n+\frac{1}{2})x}{2\sin(\frac{1}{2}x)}$ for any $x\in\Bbb R$

So I'd like to prove that for any $x\in\Bbb R$ the formula $$ \frac{1}{2} + \sum_{k=1}^n\cos(kx) = \frac{\sin\Big((n+\frac{1}{2})x\Big)}{2\sin\frac{x}{2}} $$ holds. First of all we observe that the ...
1
vote
1answer
31 views

Powers of a Toeplitz matrix

I'm searching a closed formula to compute the powers of the following matrix \begin{equation*}F\triangleq \begin{bmatrix} 1 & T & \frac{T^2}{2}\\ 0 & 1 & T\\ 0 & 0 & 1 \end{...
1
vote
2answers
39 views

AM-GM inequality proof explanation

I am reading a proof (see page 2) of the following statement. Let $n\in \mathbb{R}$ and suppose we are given real numbers $a_1\geq a_2\geq \dots a_n\geq 0$. Then $$ \frac{1}{n}\sum_{i=1}^n a_i\geq \...
1
vote
2answers
42 views

Well Ordering implies Induction Proof doubt

I’m trying to understand the proof for the fact that that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, if S ⊂ N such that 1 ∈ S and n + 1 ∈ S whenever n ∈ S,...
1
vote
0answers
31 views

Prove that a sum involving any number of vectors is independent of the way they are combined and associated

I am trying to prove the following statement from my course book: A sum involving any number of vectors is independent of the way/order they are combined and associated. A hint was given that a clever ...
0
votes
0answers
61 views

How to prove $p(f(f(X)))$ or $AX:p(f(X)) \implies p(f(f(X))))$, given that $AX:(p(X) \implies p(f(X)))$

I have the following: Objects: $a$ Functions: $f$ Now, the following are the premises: Premises: $p(a)$ $AX:(p(X) \implies p(f(X)))$ In other words, $p(a)$ $\forall X.(p(X) \implies p(f(X)))$ Now, how ...
0
votes
0answers
53 views

need help undertanding the strong form of induction

I was learning the strong form of induction, and given the following definition: Sometimes it is necessary to use the following “strong” induction using a “stronger” (albeit equivalent) hypothesis. ...
0
votes
1answer
32 views

How to read second point of Axiom of Induction

I have two questions: How do you read the following expression in words: (here is $A\subseteq \mathbb{N}$) $\forall k\in \mathbb{N}(k\in A\implies k+1\in A)$? What I would translate it as is: for ...
0
votes
1answer
44 views

Prove using induction: $\sum_{i=1}^{n}\frac{(-2)^i}{i}\leq 2^{n-2}$ $\forall n \in \mathbb{N}$

I already checked it holds for $n=1$. So let's suppose $\sum_{i=1}^{n}\frac{(-2)^i}{i}\leq 2^{n-2}$ holds for $n \in \mathbb{N}$, then we want to show that $\sum_{i=1}^{n+1}\frac{(-2)^i}{i}\leq 2^{n-1}...
2
votes
1answer
90 views

Question abut the ambiguity of a maths problem.

I am trying to prove by induction that: $$1^3-2^3 +\cdots+n^3=(1+2+\cdots+n)^2 $$ This was a problem from a practice worksheet, but I don't understand how to interpret the LHS. Is the following ...
1
vote
1answer
38 views

Proof that either $G$ or its complement $\bar{G}$ is connected by induction

I wrote the following inductive proof, but I don't know if it is valid and if there are any points that I'm missing. I got a bit lost trying to prove the inductive step. We prove this statement by ...
0
votes
1answer
66 views

Equivalence of weak induction

Let $P(n)$ be an open statement about $n\in \mathbb{N}$. In the weak induction, beside the base case, it is stated: $\forall k\in \mathbb{N}(P(k)\implies P(k+1))$$\qquad (i)$ But, in this page right ...
1
vote
1answer
169 views

Confusion on my inductive proof of $2^n$ ≥ $n^2$ for n ≥ 4 [closed]

(The problem) Use the principle of mathematical induction to prove that $2^n$ ≥ $n^2$ for n ≥ 4 Here's my solution on paper (https://i.stack.imgur.com/iJq7M.jpg) (1) The Basis case is true: for n = 4 ...
-1
votes
2answers
53 views

Solving non-homogeneous recurrence relations [closed]

Find $g_{n}$ if $g_{n+2}-6g_{n+1}+9g_{n}=3\times 2^n + 7\times (3)^n$ given $g_{0}=1,g_{1}=4$. How can I proceed to solve these kind of recurrence relations? I cannot show any work since I haven't ...
0
votes
0answers
44 views

Please Check My Proof of Well-Ordering Principle using Induction

Well-Ordering Principle: $\exists m \in A[\forall n \in A (m \in n \vee m = n) ]$ for all $A \subseteq w$ where $w$ is the set of natural numbers and $A \neq \phi$. Base Case: $A_{1} = \{ e_{1} \}$ is ...
0
votes
1answer
47 views

How to prove $(1+q)^n \geq1+qn$ for all $\mathbb{N}$ with $q>0$

I need to prove $(1+q)^n \geq1+qn$ for all $n \in \mathbb{N}$ with $q>0, q\in \mathbb{R}$ using mathematical induction. Firstly, I proved the base case for $n=1$ that indeed $1+q\geq1+q$. Then in ...
3
votes
1answer
37 views

Fubini and induction for a sum over a set $Q$

How to calculate $$ \int_{Q}\left(x_{1}+x_{2}+\ldots+x_{n}\right)^{2} d \lambda_{n} $$ whereas $n \geq 2$ and $$ Q=\left\{\left(x_{1}, \ldots, x_{n}\right) \in \mathbb{R}^{n}: 0 \leq x_{i} \leq 1, i=1,...
2
votes
1answer
210 views

Showing that the sequence $a_{n+3}=5a^6_{n+2}+3a^3_{n+1}+a^2_n$, with $a_1=2019$, $a_2=2020$, $a_3=2021$, contains no numbers of the form $m^6$

Here's a problem that I couldn't solve in a recent olympiad in which I took part. The problem says The sequence of real numbers $a_1$, $a_2$, $a_3,\cdots$ is defined as follows: $a_1 = 2019,$ $a_2 = ...
0
votes
0answers
33 views

What does it mean by Strong principle induction is equal to Weak principle induction?

In the proof of the equivalence of SPI and WPI, it is said that SPI implies WPI and WPI implies SPI. But WPI and SPI are just proving techniques, what does it mean by one proving technique implying ...

1
2 3 4 5
185