Skip to main content

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
0 answers
31 views

I need help with mathematical induction on trigonometry [closed]

I need to prove that $\cos x \cos 2x \cos 4x \ldots \cos 2^{n}x= \sin 2^{n+1}x/2^{n+1}\sin x$ while $x \in \mathbb{R}$.
milica's user avatar
  • 9
0 votes
2 answers
91 views

Proof by induction $\sum_{k=1}^n k \cdot 2^k \leqslant n\cdot (2^{n+1} - 1)$ for $n \in \mathbb{N}$

Task Proof by induction $\sum_{k=1}^n k \cdot 2^k \leqslant n\cdot (2^{n+1} - 1)$ for $n \in \mathbb{N}$ What I got so far Induction start For $n=1$ one can show that $2^1 \leqslant 1 \cdot (2^{1+1}...
lmixa's user avatar
  • 31
0 votes
1 answer
67 views

Why can't you prove by induction that $\left(\bigcup_{n = 1}^{\infty}A_n \right)^C = \bigcap_{n = 1}^{\infty}A_n^C$?

In the solutions to Exercise 1.2.12 of his Understanding Analysis, Abbott states that it is not possible to prove using induction that $$\left(\bigcup_{n = 1}^{\infty}A_n \right)^C = \bigcap_{n = 1}^{\...
Riccardo Iorio's user avatar
0 votes
2 answers
146 views

How to justify why succession and addition cannot be circularly defined like this?

I am reading Tao's Analysis I, in which he states: One may be tempted to [define the successor of $n$ as] $n + 1$. . . but this would introduce a circularity in our foundations, since the notion of ...
Princess Mia's user avatar
  • 2,495
0 votes
2 answers
39 views

Prove that the only natural value of $g$ that makes $8g+4p^2-4p+1$ ($p\in\mathbb{N}$) a perfect square is $g=p$

This problem came up while I was working on a larger problem and I've looked at a few different ways of solving it, the main approach being mathematical induction; however, I've been unable to prove ...
b_rop's user avatar
  • 64
0 votes
2 answers
63 views

Why does the principle of mathematical induction work for integers?

I took a course on the foundations of mathematics a while ago and we went through the construction of the natural numbers and then the integers. We did prove the principle of mathematical induction (...
nazorated's user avatar
0 votes
1 answer
62 views

Stuck on the induction step in a proof for $(x+\frac{1}{x})^n$

Background I was playing around with the function $y=x+\frac{1}{x}$ and noticed the following pattern: $x^2+\frac{1}{x^2}=y^2-2$ $x^3+\frac{1}{x^3}=y^3-3y$ The issue I am trying to prove $x^n+\frac{1}{...
Red Five's user avatar
  • 2,671
-2 votes
2 answers
139 views

Why is addition not completely defined here?

Say for the natural numbers, we define addition this way: $0 + 0 = 0$, and if $n+m = x$, then $S(n) + m = n+S(m) = S(x) $ Say we have the regular Peano axioms, except we delete the axiom of ...
Princess Mia's user avatar
  • 2,495
1 vote
2 answers
130 views

Is it circular to include reachability from $0$ like this as a Peano axiom?

I am wondering whether it makes logical and semantic sense to include, as an axiom to define the natural numbers, that "every natural number is either $0$ or the result of potentially repeated ...
Princess Mia's user avatar
  • 2,495
-1 votes
0 answers
70 views

Does the axiom of induction hold iff every natural number is either $0$ or is the result of repeated successor operations on $0$? [closed]

I am wondering whether we could replace the axiom of Induction with an axiom saying that every natural number is either $0$ or can be expressed as repeated successor operations from $0$ (keeping all ...
Princess Mia's user avatar
  • 2,495
0 votes
1 answer
32 views

Understanding proof of Hall's graph theorem

I am struggling with understanding proof of Halls theorem. Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
Jane Doe's user avatar
  • 129
-2 votes
2 answers
177 views

Can we modify the Peano axioms like this? [closed]

I am wondering if the following modifications of the Peano axioms result in a set of axioms equivalent to the Peano axioms, in the sense that any set of numbers satisfies these modified axioms if and ...
Princess Mia's user avatar
  • 2,495
-2 votes
0 answers
32 views

Induction proof for a recursive formula [closed]

Let $b_1,\dots,b_n\geq 0,\lambda>0$. Let $z_i=\lambda\sum_{j=0}^{i-1}b_{i-j}z_j$ with $z_0=\lambda$. Show that $z_i$ can be computed as: $z_i=\sum_{j=0}^{i}a_{ij}\lambda^{j+1}$ with $a_{ij}=\sum_{k=...
andy's user avatar
  • 355
3 votes
1 answer
52 views

What is the Euclidean norm of the vector containing all $k$-order partial derivatives of $|x|$?

Denote $|x|$ the Euclidean norm of a vector $x\in\mathbb R^N$. Also denote $D^kf$ as the vector in $\mathbb R^{N^k}$ containing all $k$-order partial derivatives of the function $f\colon\mathbb R^N\to\...
Raoní Cabral Ponciano's user avatar
1 vote
1 answer
51 views

How to describe this identity in words? [closed]

Whenever I write an induction proof, I try to give it a word-description. Sometimes it's hard to describe the identity proven. This one, for example, $$2\cdot1 + 3\cdot2 + 4\cdot2^2 + 5\cdot2^3 + \...
user1145880's user avatar
0 votes
0 answers
41 views

Induction on two variables, confused about the induction step

Suppose I want to show For any $n>1$, any $r$, such that whenever $r+1 \leq n$, we have $P(n,r)$. (Geometrically, we have a 'infinite' triangle in the plane) My induction goes as $\forall n >1$ (...
Andrew_Ren's user avatar
-1 votes
0 answers
31 views

Use structural induction to show that if $n \in S,$ then $n \equiv 4 \pmod 6$ [duplicate]

I am working an a task regarding structural induction. The task is as follows: Let S be the set of positive integers defined recursively by Basis step: $4 \in S$ Recursive step: If $n \in S$, then ...
felland's user avatar
0 votes
1 answer
39 views

Question concerning induction [duplicate]

This might be a stupid question: I recently did a question concerning some polynomials and I was supposed to calculate $(X^n-1) \div (X-1)$. It was supposed to be done by induction on $n$ but I kind ...
metamathics's user avatar
0 votes
2 answers
52 views

How to rewrite this algebraic equation so that its factorization ends up obvious? [closed]

While working on an induction exercise, I had $k(2k + 1) + 6(k + 1)$ and I wanted to express that as $(k + 2)(2k + 3)$. I couldn't do it without expanding the first expression. I had to write $$k(2k ...
user1145880's user avatar
0 votes
1 answer
67 views

Proving that the set of non-negative half-integers satisfies Peano's axioms

I postulate that the following set $\{0,0.5,1,1.5,...\}$ represents the natural numbers. Of course, intuitively, this isn't true. But let me try to show this using Peano's axioms. I'll first define ...
Ryan's user avatar
  • 159
1 vote
0 answers
28 views

Prove one specific Upper bound of the minimum time of a p-processor schedule

In spring18 mcs.pdf, it has Problem 10.26: We want to schedule n tasks with prerequisite constraints among the tasks defined by a DAG. (a) Explain why any schedule that requires only p processors ...
An5Drama's user avatar
  • 390
0 votes
0 answers
43 views

Mathematical Induction, coin problem

Show that any amount in cent greater than or equal to 6 can be obtained using 2 cents and $b$ cents coins. Prove with the help of strong mathematical induction. Note: First find the correct value of $...
Ali's user avatar
  • 1
0 votes
1 answer
58 views

The state machine for "Extended Euclidean Gcd Algorithm" terminates after at most the same number of transitions as that of the Euclidean algorithm

This is one following question based on one question I asked before In spring18 mcs.pdf, it has Problem 9.13: Define the Pulverizer State machine to have: $$ \begin{align*} \text{states} ::=&...
An5Drama's user avatar
  • 390
1 vote
3 answers
91 views

A simpler way for proving $4^{2n+1} + 7^{2n+1}$ is divisible by $11$?

Does my induction step seem correct? My logic is to split up this step into two parts and then bring them together to prove its divisible by $11$. It does seem very messy and I'm wondering if there is ...
coolcat's user avatar
  • 147
1 vote
0 answers
54 views

Proving recurrence relation by mathematical induction(related to merge sort) [duplicate]

I have the following recurrence relation: $T(1) = 1$ $T(n) = T(\lfloor n/2\rfloor) + T(\lceil n/2 \rceil) + n$ When proving by induction,by assuming that $n=2^k$ for some $k \in \mathbb{N}$ I get ...
csmathstudent8's user avatar
2 votes
0 answers
66 views

the Ackermann function must be total and unique based on one specific list of rules

This is one following question based on one question I asked before. In mcs.pdf, it has Problem 7.25 in p251(#259). One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
An5Drama's user avatar
  • 390
0 votes
1 answer
79 views

Show that $A = \mathbb N$.

I have a question regarding the following exercise: "Let $A \subseteq \mathbb N$ with the following properties: $1 \in A$ and $\forall n\in A$ it ist true that $2n \in A$ and $2n+1 \in A$." ...
klonedrekt's user avatar
-1 votes
1 answer
64 views

Prove that $\sum_{j=1}^r{\prod_{i=0}^{k-2}(j+i)\over (k-1)!} = \frac{\prod_{i=0}^{k-1}(r+i)}{k!}$ [duplicate]

Prove that $$\sum_{j=1}^r{\prod_{i=0}^{k-2}(j+i)\over (k-1)!} = \frac{\prod_{i=0}^{k-1}(r+i)}{k!}$$ where $k\in\Bbb N , k\ge2$ Example) $$k=2:\sum_{j=1}^rj= \frac{r(r+1)}{2!}$$ $$k=3:\sum_{j=1}^r\frac{...
TH_Lee's user avatar
  • 17
3 votes
1 answer
88 views

Find $\sum_{n=1}^{2024} g_n\left(\frac{1}{\sqrt{n+1}}\right)$, where $g_n$ is defined recursively.

Problem Statement Given a function $f(x)=x^2$, define $g_1(x)=f(x)$ and subsequently; $g_{n+1}(x)=\min_{t\in\Bbb R}(g_n(t)+f(x-t))$, where $n\in\Bbb N$. Find : $\sum_{n=1}^{2024}g_n\left(\frac{1}{\...
aditya's user avatar
  • 89
0 votes
1 answer
44 views

Help on Prove by induction, $n=a+1$ case simplification [duplicate]

I've been stuck on this question for a bit, I am unsure of how to factorize factorial and is stuck at this stage. If someone can give me a hint on where to go next, it would be highly appreciated! $$\...
Kitty Summoner's user avatar
0 votes
1 answer
80 views

partial function version of the Ackermann function must be total

In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
An5Drama's user avatar
  • 390
0 votes
0 answers
34 views

Induction proof on a linear function [duplicate]

Am I on the right track with my attempt at the following problem? Show that for all $n \in \mathbb{N}$ with $n \geq 8$ there exist $k, l \in \mathbb{N}$ such that $n=3 k+5 l$. Hint: Use not only $n=...
K-1's user avatar
  • 1
0 votes
1 answer
53 views

Mathematical Induction: Strong vs Weak Form

I have a rather naive question: The usual mathematical induction works by the same scheme: Let $n_0 \in \mathbb{N}$ a pos integer and $A(k), n_0 \le k \in \mathbb{N}$ family of statements. Then the &...
user267839's user avatar
  • 7,129
-1 votes
2 answers
77 views

How can I prove by induction that $2^{2^n}>n^n $?

How can I prove that: $2^{2^n}>n^n$ for any $n\in \mathbb N$? My trying: I tried to use induction, of course it worked to $n=1$. Then $n=k$, and $2^{2^k}>k^k.$ I assumed that as a true and ...
lyla venom's user avatar
0 votes
1 answer
85 views

Proving a question about Mathematical Proof by Induction

The question has been taken from the 1998 National Mathematical Contest. The problem is from the Canada team. Let $n$ be a natural number such that $n\ge2$. Show that $$ ({\frac {1}{n+1}})× (1+{\frac ...
tahasozgen's user avatar
1 vote
0 answers
26 views

Determining initial algebras and final coalgebras for a given functor without using limits/colimits

I'm trying to find the final coalgebra for a certain functor but I have no idea how to do that in general, so I was hoping to go through the process with some simpler examples. In section 4.1, The ...
msb15's user avatar
  • 138
5 votes
2 answers
205 views

Understanding inductive proof of $\sum_{{m=k}}^{N} {m\choose k} = {N+1\choose K+1}$

I am an engineering student and am trying to prove the following combinatorics identity in math: $$\sum_{{m=k}}^{N} C(m,k) = C(N+1, K+1)$$ It was suggested to me to use Proof By Induction so I tried ...
konofoso's user avatar
  • 521
0 votes
0 answers
43 views

Induction proof for product of $a^x$ is less than or equal to the sum of $x\times a$

So this type of problem has me stuck in proving some relation. I assumed to use induction but I am stuck at a certain step and cannot understand if there is a trick or perhaps my idea is just wrong: ...
thewhale's user avatar
0 votes
0 answers
57 views

Set theoretic definition of terms of the untyped lambda calculus

I am trying to translate the following definition (in Agda) of intrinsically scoped terms of the untyped lambda calculus into more mathematical (in particular set theoretical) notation: ...
user11718766's user avatar
2 votes
1 answer
110 views

Proving Munkres Theorem 51.3

I am trying to prove Theorem 51.3 from Munkres, that is: Let $f$ be a path in $X$ and let $a_0, \dotsc, a_n$ be numbers such that $0 = a_0 < a_1 < \dotsb < a_n = 1$. Let $f_i\colon I \to X$ ...
JLGL's user avatar
  • 559
0 votes
1 answer
26 views

Characterizing congruences on the algebra of natural numbers

I'm trying to do Exercise 31 in Jan Rutten's book on coalgebras. The goal is to show that, given a characterization of congruences on the initial $N$-algebra $(\mathbb{N},[\text{zero},\text{succ}])$, ...
msb15's user avatar
  • 138
1 vote
1 answer
185 views

Is this proof for mathematical induction valid?

Instead of beginning from the natural numbers, we first define $\mathbb R$ using field axioms. Let $\mathscr H$ be a set of subsets of $\mathbb R$ defined as follows: $$\mathscr H = \{H \subset \...
Elvis's user avatar
  • 455
0 votes
0 answers
74 views

Why seemingly wrong proof works in proving $\varphi^{n+1} = \varphi \cdot F_{n+1} + F_n$ by induction?

I was reading this post on this site. Which says: Fibonacci Rules: \begin{align*} F_0 = 0 && F_1 = 1 && F_{n+2} = F_n + F_{n+1} \end{align*} Prove, by induction, that $\varphi^{n+1} ...
Etemon's user avatar
  • 6,653
1 vote
1 answer
89 views

Sequence $f(k)=\underbrace{\sqrt{m+\sqrt{m+\sqrt{m+\cdots}}}}_{\text{$k\ m$'s}}-\underbrace{\sqrt{m-\sqrt{m-\sqrt{m-\cdots}}}}_{\text{$k\ m$'s}}$

Define $$f(k)=\underbrace{\sqrt{m+\sqrt{m+\sqrt{m+\cdots}}}}_{\text{$k$ $m$'s}}-\underbrace{\sqrt{m-\sqrt{m-\sqrt{m-\cdots}}}}_{\text{$k$ $m$'s}}$$ Given $m$ and $k$ are integers such that $m\ge1$ and ...
Sankalp Kumar Jha's user avatar
1 vote
1 answer
87 views

Proof by induction in the Baker–Campbell–Hausdorff formula

Whilst studying Commutators, I stumbled across this post in which the Baker–Campbell–Hausdorff formula is being proven. In one of the answers, it is stated that a certain step can be proven by ...
haifisch123's user avatar
0 votes
0 answers
42 views

What is the volume of the multivariate normal distribution in the positive orthant?

I want to know the formula of the volume of the multivariate normal distribution in the positive orthant. For example, when there is only one variable, like $X\sim N(0,1)$, then $P(X>0)=\frac{1}{2}$...
Heh Jah's user avatar
0 votes
0 answers
60 views

Proving the number of edges by Induction

Let there be a simple graph denoted $B_{n}$. There are $2^n$ vertices in $B_{n}$, and each vertex is labelled with a binary string of length $n$. Two vertices are adjacent if the bitwise-or (inclusive ...
PsychBit's user avatar
1 vote
4 answers
96 views

How to prove $\forall a \gt 0, \exists N\in \Bbb Z^+, \forall n \gt N, a^n \lt n!$ [closed]

I know that for a specific $a$, inequations like $2^n<n!$ can be easily proved by induction. But when it comes to a common $a$, Idk how to derive from it especially about finding the first element ...
Wazz's user avatar
  • 47
0 votes
1 answer
38 views

Is a geometric series weighted average less than the mean average?

Suppose I have an infinite sequence $\{a_i\}_{i=1}^\infty$ where $a_i \in [0,1]$ for all $a_i$. Next let \begin{align*} f(n) &= \sum_{i = 1}^n\frac{1}{2^i}a_i\\ g(n) &= \frac{1}{n}\sum_{i = 1}^...
Kookie's user avatar
  • 510
0 votes
1 answer
62 views

Is there a induction proof that $\gcd(a,b) = \gcd(b, a \bmod{b})$?

I know how to prove the equation $$\gcd(a,b) = \gcd(b, a \bmod{b}).$$ But I don't use induction. I don't find it natural to use induction in this case because I usually think of induction when a ...
user1145880's user avatar

1
2 3 4 5
204