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
44 views

Prove that if $4k+1$ is a prime number than for every $n \in \mathbb{N}$ $\sum\limits_{j=1}^{2k}{j^{4n+2}}$ is a multiple of $4k+1$

Prove that if $4k+1$ is a prime number than for every $n \in \mathbb{N}$ $\sum\limits_{j=1}^{2k}{j^{4n+2}}$ is a multiple of $4k+1$ First I tried proving for n=1 $\sum\limits_{j=1}^{2k}{j^{6}}=(4k+1)...
1
vote
1answer
52 views

beginner with induction, something I don't understand

I have to prove the following using induction: $1^3 + 2^3 + 3^3 + ... + n^3 = \dfrac{n^2(n + 1)^2}{4} $ I understand the base case: we just replace n with 1 and we end up with 1 = 1, so $n=1$ is ...
2
votes
1answer
30 views

Prove the following statements about the geometric sum.

Prove the following two statements: $\Sigma^n_{i=0}q^i=\frac{q^{n+1}-1}{q-1}, n \in \mathbb{N}, q\neq1$ For a number $q$ with $|q|<1$, $\Sigma^ ∞_{i=0}q^i = \frac{1}{1-q}$ is true. The first part ...
2
votes
1answer
38 views

Questions about induction and Big O

Statement: For any $k \in \mathbb N$, the value of $\displaystyle{\sum_{i=1}^ni^k}$ is a polynomial in $n$ with the leading term $\displaystyle{\frac{1}{k+1}n^{k+1}}$ and next term $\displaystyle{\...
0
votes
0answers
43 views

Proving $1 + 2 + 2^2+2^3 + 2^4 + \dots+ 2^{n-1}= 2^n -1$ using mathematical induction [duplicate]

I'm taking Pre-Calc, and if anyone could go through step-by-step on this problem I’d appreciate it greatly. ;) Use mathematical induction to prove the formula for every positive integer n. $$1 + 2 + ...
1
vote
1answer
32 views

Proving $\frac{b-a}{b-x}\cdot (\frac{b-a}{k+1})^{k+1}\geq (\frac{b-a}{k})^{k+1}$

Prove that: $$ |\prod_{i=0}^n(x-x_i)|\leq\frac{n!}{4}(\frac{b-a}{n})^{n+1} $$ where $x_i=a+i\frac{b-a}{n}$ for $i=0,...,n$ and $x\in [a;b]$ I have tried to do induction: I proved it for $n=1$ and now ...
1
vote
1answer
74 views

Induction based on the 2-cocycle identity for $c': \Bbb Z/p \times \Bbb Z/p \to \Bbb Z/p$ and $c'(0, 0) = 0$

Context: I was trying to find the number of elements in $H^2(C_p; \Bbb Z/p)$ and my professor gave this hint (cf. Understanding the relation between central extensions and 2-cocycles and coboundaries)...
1
vote
1answer
23 views

Proof by induction of number of edges in complete (fully connected) graph

I tried to use induction to prove that the number of edges in a graph of $n$ nodes is $\frac{n (n-1)}{2}$. Does the following work? Assume that a graph of $n$ nodes, where $n \geq 2$, has $\frac{n (...
1
vote
1answer
18 views

Sylvester matrix column orthogonality

I wanted to prove by induction that all sylvester Matrices defined below have orthogonal columns, which seems trivial to see but I wanted a rigorous proof. $H_0$ = [1] , $H_{i+1}$ = \begin{matrix} ...
1
vote
1answer
31 views

Prove by induction $u_{n+2}+u_n=4u_{n+1}$ for all $n\in \mathbb{N}$, where $u_n=(2+\sqrt{3})^n+(2-\sqrt{3})^n$.

Prove by induction $u_{n+2}+u_n=4u_{n+1}$ for all $n\in \mathbb{N}$, where $u_n=(2+\sqrt{3})^n+(2-\sqrt{3})^n$. For $n=1$, My efforts: LHS= $u_3+u_1=(2+\sqrt{3})^3+(2-\sqrt{3})^3+ (2+\sqrt{3})^1+(...
2
votes
2answers
60 views

Use Mathematical Induction to prove that for all integers $n\geq 5, 1+4n<2^n$

So far I have gotten this far: Proof: Let $S(n)$ be the statement above $S(n)=n\geq 5,1+4n<2^n$ ...
0
votes
1answer
48 views

Induction proof: Prove that $(1+x)^n \geq \frac{n(n-1)(n-2)}{6}x^3$ for $n\geq 3$

I'm stuck on this proof. I assume it's supposed to be an induction proof, but I cannot figure out how to algebraically prove that $(1+x)^{k+1}\geq \frac{(k+1)(k)(k-1)}{6}x^3$. Any help would be ...
0
votes
0answers
25 views

why does $4n-1$ specifies index of a set?

Hi I'm following a course on mathematical induction, and I found something that doesn't quite make sense to me The professor gave os this statement: $$3+7+11+\cdots+(4n-1) = n(2n+1)$$ then he goes ...
0
votes
1answer
30 views

Using strong mathematical induction to prove a statement

So I have a question that I got stuck on, it says I have to prove that all integers greater than 17 can be written using a sum of 7's and 4's. For instance 7 + 7 + 7 + 4 + 4 = 29 or 7 + 4 + 4 + 4 = 19 ...
0
votes
1answer
29 views

prove $|A\times B|=|A|\times|B|$ using induction

Prove that |A × B| = |A| × |B| for finite sets A, B. What should be the base case for this? ALso, for the inductive step, if I take |A|=m and |B|=n, then should I take |A|=m+1 and |B|=n+1 and prove ...
0
votes
1answer
13 views

Proving convergence for recurring sequence? [closed]

I have been trying to use induction to prove that a recurring sequence is monotone, but the problem that I'm having is that no initial values are given. Can someone please give a hint as to how to ...
0
votes
2answers
45 views

Prove or disprove: The recursive sequence $(a_{n})_{n=1}^\infty: a_{n+1} = -3 - a_{n}^2, a_1 = 2$ converges

My intuition is that this sequence is not convergent. I started by proving with induction that the sequence is strictly decreasing: Base case: $n = 1, a_1 = 2$ $n = 2, a_2 = -3 - (2)^2 = -7 < ...
0
votes
2answers
39 views

Prove that $\cosh x > x$

I am attempting to prove that $\cosh x > x$ for all values of $x$. I have proven it by induction but I don't think that would suffice since proof by induction only covers integers. Also, from a ...
4
votes
5answers
172 views

Fibonacci recurrence relation - Principle of Mathematical Induction

The problem: Let $F_n$ be the nth term of the Fibonacci sequence: $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ for $n\geq2$ Prove that $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$ for ...
3
votes
1answer
68 views

Length of the well formed formula $(((p_0)\rightarrow ((p_1)∧(p_{32}))) \rightarrow ((((p_{13})∧(p_6))∨(p_{317})) \rightarrow (p_{26})))$

How is the length of this well formed formula defined as $5$? $\big(((p_{0})\rightarrow ((p_1) \land (p_{32}))) \rightarrow ((((p_{13}) \land (p_6)) \lor (p_{317})) \rightarrow (p_{26}))).$ (from ...
0
votes
2answers
56 views

Prove that every positive integer can be expressed as a product of odd number and power of $2$.

Prove that every positive integer can be expressed as a product of odd number and power of $2$. In other words, prove that for $n \ge 1$, $!h \in \mathbb{Z^+}$, $h$ odd, and $k \in \mathbb{Z}$, $k \ge ...
3
votes
1answer
81 views

Are there any strong forms of “clamped” induction?

So in normal induction, we say that if $P(a)$ is true, and $P(n)\implies P(n+1)$, then $P(n)$ is true $\forall n\geq a$. Then we have strong induction where you assume all preceeding values of the ...
0
votes
1answer
34 views

A problem with proving an inequality

How would i prove the following inequality: $\frac{1}{\sqrt{2}}+\frac{1}{(\sqrt{2})^2}+\cdot\cdot\cdot+\frac{1}{(\sqrt{2})^n}\leq\frac{1}{\sqrt{2}-1}, \forall n\in\mathbb{N}$. Maybe the inequality ...
0
votes
1answer
36 views

Sequence problem by strong induction.

I believe I should solve the following by strong induction since it's discrete mathematics, but I don't know how to do it. Given this sequence: $a^{}_{1}=2$ $a^{}_{2}=3$ $a^{}_{n}=2a^{}_{n-1}-a{}...
0
votes
1answer
44 views

There exists a scalar $k$ such that $T^{2018}$ = $k^{2017}T$

Let $T$ be a linear transformation on a finite-dimensional vector space $V$ with dimension of $V$ being $d \geq2$. Given that $\text{rank}(T) = 1 $, prove that there exists a scalar $k$ sucht that $T^{...
1
vote
0answers
23 views

Is the following argument based on recurrence relations and floor functions valid?

Is the following inductive argument with recurrence relations valid? Let: $x > 0$ be a real $t > 0$ be an integer $p_n$ be a $n$th prime $W_n(x)$ be the following recurrence relation: $...
0
votes
1answer
26 views

Question regarding initial segment and transfinite induction.

Suppose $X$ is an uncountable well-ordered set with $\leq$.For $x\in X$ ,define the initial segment of $X$ determined by $x$ as $I(x)=\{y\in X| y\leq x $ and $y\neq x\}$.Now my question is ,does there ...
1
vote
1answer
32 views

Find the mistake in the following proof by induction (exercise in AOC, Vol.1, Knuth)

In the Art Of Programming by Knuth there is the following exercise: There must be something wrong with the following proof. What is it? "Theorem. Let $a$ be any positive number. For all positive ...
0
votes
3answers
39 views

Proof sequence by induction

I have the following problem I am not sure about. Let n = 0, 1, 2, ... and show that the equation $a_0 = 1, a_{n+1} = 2a_{n} + 1$ has the solution $ a_n = 2^n - 1$ Base case: $ n = 0 \\ a_0 = 2^0 - ...
1
vote
1answer
15 views

Proving that for every n there exists one step codes from 0 to 2^(n)-1 (Gray Code)

Prove that for every n ∈ N with n ≥ 1 exists a one step binary code Cn for the number interval [0..2 n −1] with code words of length n. I have the hint of complete induction. So my start would be ...
0
votes
2answers
43 views

Show the equality between a product and a sum of products

Let $A_n=\prod_{j=1}^{n}(3j-2)$, $B_n=\prod_{j=1}^{n}(3j-1)$, $C_n=\prod_{j=1}^{n}(3j)=3^n n!$. For $A_0=B_0=C_0=1$. Show that $C_n=\sum_{k=0}^{n}$${n}\choose{k}$$A_k B_{n-k}$. I've tried to prove ...
2
votes
3answers
43 views

Use mathematical induction to prove that for all integers $n \geq 3,\, 2n + 1 < 2^{n}$

This is what I've got so far. Let $P(n)$ be the statement that $2n + 1 < 2^n$ Basis: Let $n = 3$. Show that $P(3)$ is true. $2(3) + 1 = 7$ and $2^3 = 8$. Since $7 < 8$, $P(3)$ is true. ...
0
votes
0answers
38 views

Proof by Induction (MIT open courseware)

I'm currently working through MIT's 6.042 practice problem sets. One of the problems, called "Surveyevor" has me completely flummoxed. I tried and failed, so had a look at the solution and still ...
0
votes
1answer
15 views

How to prove that for $n-th$ dimension vectror coordinate substitution, the order of key is $n!$

First of all, I don't know how this method (in cryptography) is called in English. But the idea is that if we use as a cipher a vector with three coordinates, we can align these coordinates in 3! ways....
5
votes
2answers
208 views

Is this a good enough proof by induction?

I am trying to understand induction. Is the proof good enough to satisfy what was looked for? If not, do you have any feedback for me? To show: $\sum_{i=0}^n i^2 ≤ n^3$ for any $n = 0, 1, 2,\ldots$ ...
1
vote
1answer
36 views

Counting matchings in k-regular bipartite graphs

I have a math problem that states the following: Problem: Show that a k-regular bipartite graph G = (S+T, E) contains at least k! matchings with |S| = |T| number of edges. Solution: So far I have ...
1
vote
2answers
49 views

Is $\displaystyle \sum_{k = 1}^n\frac{1}{k^2} \leq 2 -\frac{1}{n}$ correctly proved by induction?

I have this statement: Prove by induction that $\displaystyle \sum_{k = 1}^n\frac{1}{k^2} \leq 2 -\frac{1}{n}$ for $n \in \mathbb{N}$ My attempt was: Base case: $\frac{1}{1} \leq 1$ Assume that $...
1
vote
1answer
39 views

Boolean Algebra: Self-dual Boolean Function $g(x) = \lnot f(\lnot x)$

Q) For $x \in \{0,1\}$, let $\lnot x$ denote the negation of $x$, that is $$\lnot \, x = \begin{cases}1 & \mbox{iff } x = 0\\ 0 & \mbox{iff } x = 1\end{cases}$$. If $x \in \{0,1\}^n$, then $\...
2
votes
2answers
43 views

Mathematical induction: propper use of assumption?

Let $u_n$ be any recursive expression containing $u_{n-2}$. We are trying to prove that $u_n= f(n)$, where $f(n)$ is any well defined and not recursive expression of $n$. Let's assume we know $u_1=f(...
1
vote
0answers
27 views

Is the following inductive argument valid for establishing the relationship between two recurrence relations?

Is the following inductive argument valid? Let: $x$ be a positive real $n,t \ge 1$ be an integers $p_n$ be the $n$th prime $p\#$ be the primorial of $p$ gcd$(a,b)$ is the greatest common divisor ...
2
votes
2answers
57 views

$a+a^2+\cdots + a^{2n} ≤ n(a^{2n+1} + 1)$

Let $a \geq 0 $ and $n \in \mathbb{N}$, prove $$a+a^2+\cdots + a^{2n} ≤ n(a^{2n+1} + 1)$$ I tried induction, but it didn't deliver a lot of results.
1
vote
0answers
20 views

Fibonacci numbers induction proof [duplicate]

I recently found out that the Fibonacci Sequence appears in the Pascal Triangle. If it is written like so: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 etc. If we sum the diagonals, we get: $1 = 1 $ $1 = 1 $ ...
0
votes
2answers
32 views

Define a sequence $a_0 = 2$ and $a_1 = 4$ and $a_n := 2a_{n-1} - a_{n-2} + 6 $ for $ n \geq 2.$ Prove that $a_n = 3n^2 - n + 2.$

Proof. We proceed by strong induction on n. Observe that $a_0 = 2 = 3(0)^2 - 0 + 2$ and $a_1 = 4 = 3(1)^2 - 1 + 2.$ Assume that there is an integer k such that $a_j = 3j^2 - n + 2$ for all $2 < j ...
0
votes
3answers
51 views

How to use factorisation $z^{n}-1$ to prove the summation goes to zero?

I need to show that $\sin(\frac{2\pi}{n})+\sin(\frac{4\pi}{n})+...+\sin(\frac{2(n-1)\pi}{n})=0$ for $n>1$ but specifically using the fact that $z^{n}-1=(z-1)(1+z+z^{2}+...+z^{n-1})$ for every $z\in ...
-1
votes
3answers
59 views

Proving by induction for $n^3 - n$ is divisible by $3$ [duplicate]

Question: Prove that for any nonnegative integer $n$, $n^3 - n$ is divisible by $3$. So I suppose that $n^3 - n = 3m$ for some integer $m$. I know it is true for $n= 1$. Suppose it is true for $n=k$...
0
votes
1answer
37 views

How to prove by induction that $|z_n| \geq |c|r^{n-1}$ in complex numbers

Having $c \in \mathbb{C}$, $z_0 = 0$, $r=|c|-1$ and $z_n = z_{n-1}^2 + c$ for $n \geq 1$. Prove that if $|c| > 2$, then $|z_n| \geq |c|r^{n-1}$. I have proved that it is true for $z_1$ and $z_2$. ...
2
votes
5answers
78 views

Proof by induction: derivatives of $e^x \sin(x)$

I've been trying to work on this problem and I can't seem to solve it. Could you help? Prove by induction that: $$ f(x) = e^x \sin(x) $$ $$ f^{(n)}(x)=2^{\frac{n}{2}}e^x\sin(x+\frac{n\pi}{4}) $$ I ...
1
vote
1answer
145 views

Find all $f$ such that $f\left(m^{2}+n^{2}\right)=f(m)^{2}+f(n)^{2},$

Question - Find all $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$ which satisfy (a) $f\left(m^{2}+n^{2}\right)=f(m)^{2}+f(n)^{2},$ for all $m, n$ in $\mathbb{N}_{0}$ (b) $f(1)>0$ my try - I ...
1
vote
0answers
38 views

Is there an error in this proof by induction problem?

I was asked to show by induction that " $\forall n \in \mathbb{N},-1 \cdot3+2\cdot 5-3\cdot7+...+2n(4n+1)= \alpha n $" and find the value of the constant $\alpha$. First, I rewrote the sum on the ...
1
vote
3answers
26 views

Question need to get a conjecture and prove by induction

The question is: Divide the plane into separate regions using $N$ lines according to the following rules: No two lines are parallel. No three lines intersect at the same point. When $N = 1$, the ...

1
3 4
5
6 7
160