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 ...

learn more… | top users | synonyms

10
votes
0answers
238 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 ...
8
votes
0answers
324 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
6
votes
0answers
182 views

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
4
votes
0answers
65 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
4
votes
0answers
87 views

Is this a valid statement that would imply the Collatz Conjecture?

Let $f$ denote the Collatz transformation: $f(x) = \left\{ \begin{array}{ll} {x\over 2} & \quad x\equiv 0 \mod 2 \\ 3x+1 & \quad x \equiv 1\mod 2 ...
4
votes
0answers
86 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
0answers
175 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
113 views

Transfinite induction and valuation rank

In Engler's valued fields, exercise 3.5.2 goes as follows Construct valuations on $\Bbb{C}$ of rank $\kappa$ for every cardinal $\kappa \leq 2^{\aleph_0}$. The idea behind this (for any ...
3
votes
0answers
35 views

Induction proof - not sure how to proceed with next step

Define two sequences $A_n, B_n$ as follows: \begin{align*} A_1 &= 1\\ A_2 &= 3\\ A_3 &= 2 \cdot 3+1=7 \\ A_4 &= 2 \cdot 7 + 3 = 17\\ A_5 &= 2 \cdot 17 + 7 = 41\\ A_n &= ...
3
votes
0answers
43 views

Verify my induction proof for Balanced Ternary expressions

In first place I apologize if you find a grammatical error, my English is not too good for now, but I'm work on it. That also goes for errors in my question (this is my first post). I encounter the ...
3
votes
0answers
53 views

Using induction to prove a congruence?

Let $a = 2+\sqrt{3}.$ By analogy to complex numbers let R$(a)$ be $r,$ the non-surd part of $r + s\sqrt{3}.$ I would like to show that a necessary but by no means sufficient condition that ...
3
votes
0answers
55 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
3
votes
0answers
89 views

Cauchy-Euler Equation of order $n$

What I wish to prove is that for a Cauchy-Euler equation of order $n$, the substitution $x=e^{t}$ transforms it into a linear differential equation with constant coefficients. To put it as a theorem: ...
3
votes
0answers
80 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
3
votes
0answers
533 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
2
votes
0answers
54 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
28 views

Rigor of this direct justification of mathematical induction

Proofs of a mathematical statement or theorem can have different levels of rigor and I have a question about this. In the method of mathematical induction, there are statements numbered with 1, 2, 3 ...
2
votes
0answers
97 views

Prove, using the method of mathematical induction that the following holds true

For natural numbers $n\ge1$ show the following inequality using induction. $$n^{1/n}\le 1+\sqrt{\frac{2}{n}}$$
2
votes
0answers
27 views

Confusion on particular step in this weak induction proof

I am studying for a midterm, and I came across this proof. Use mathematical induction(weak) to show that for all integers n $\geq$ 2 , if x$_{1}$, x$_{2}$, ... x$_{n}$ are strictly between 0 and 1 ...
2
votes
0answers
58 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
2
votes
0answers
86 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
2
votes
0answers
149 views

Homework Question for a 15 year old

My younger brother(age: 14 years 7 months) and his classmates were given a set of eight questions by his class-teacher, which included the following two questions: (i) Find, if you can, the fallacy ...
2
votes
0answers
135 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
2
votes
0answers
83 views

Inequality sine power series

How can we show, for $k\geq 1$ and $x \geq 0$, the inequality below by induction? $\displaystyle \sin x \geq \sum_{n=1}^{2k} (-1)^{n+1} \frac 1{ (2n - 1)! }x^{2n-1} $ The base case $k = 1$ gives ...
2
votes
0answers
99 views

Rearranging numbered cards to reverse their order

I have been thinking about this question for a long time, but I can't solve it. Here is the question: We have $9$ cards, with numbers one to nine written on them (in the order $1, 2, \ldots , 9$). ...
2
votes
0answers
44 views

How to proceed to show this hold by induction?

Show that $$\frac3{1\cdot2\cdot4}+\frac4{2\cdot3\cdot5}+\dots+\frac{n+2}{n(n+1)(n+3)}=\frac16\left[\frac{29}6-\frac4{n+1}-\frac1{n+2}-\frac1{n+3}\right],\text{ for $n\in\mathbb N$}.$$ I try ...
2
votes
0answers
140 views

geomtry and induction Discrete Math

Claim: Suppose that we draw any number of straight lines in the plane, with the restriction that no two are parallel and no intersection point belongs to more than two lines. The lines divide up the ...
2
votes
0answers
58 views

Writing down the induction principle formally

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)? $$(\exists x\in\mathbb {N}(P (x))\wedge ...
2
votes
0answers
93 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
2
votes
0answers
68 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in ...
2
votes
0answers
206 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that ...
2
votes
0answers
267 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
1
vote
0answers
43 views

Induction proof: $\det(M) = \prod_{1 \le j \le n} (x_j - x_i)$

Following problem: Let $\mathbb{K}$ be a Field and $M = \begin{pmatrix} 1 & x_1 & \ldots & x_1^{n-1} \\ \vdots & \vdots & & \vdots \\ 1 & x_n & ...
1
vote
0answers
19 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
1
vote
0answers
31 views

Exercise in induction (including double indices)

The following is for an exam preparation exercise in induction Problem: Let $f(x)=|x| = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$ and $g(x)=|x|^{2k+1}$. Let $N \leq n$ and let $k \in \mathbb{Z}$, ...
1
vote
0answers
29 views

Generalized Bernoulli's inequality of the form $\frac{1}{1-\sum_{i=1}^nx_i}\geq\prod_{i=1}^n(1+x_i)$

We got to prove the generalized Bernoulli's inequality given below for $x_1,...,x_n\geq0$ using induction. $$ \frac{1}{1-\sum_{i=1}^nx_i}\geq\prod_{i=1}^n(1+x_i)\geq 1+\sum_{i=1}^nx_i$$ The right ...
1
vote
0answers
44 views

What really is inductive reasoning?

I am looking for concrete information on "induction" in the old sense of the word. Now it is used to refer to proof by "mathematical induction"; however, I am aware that it also means inductive ...
1
vote
0answers
19 views

Proving that step-wise function is $\mathcal C^{\infty}$

I'd like a proof verification of the following, please. I want to prove that $H: \Bbb R \to \Bbb R$ is of class $\mathcal C^{\infty}$, with $H$ defined by: $$H(x) = \left\{\begin{align} &h(x) = ...
1
vote
0answers
29 views

How do I solve this recurrence relation and prove by induction?

I have this summation formula: $T(n)=\sum_{i = 1}^{n}T(n-i)T(i-1)$. Base case is $T(0)=1$, $T(1)=1$. How do I find the recurrence relation and prove it by induction?
1
vote
0answers
38 views

Proving with a given definition that if $|A|=|B|$ then $A,B$ are equivalent (with induction but without using the induction hypothesis)

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$. Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent. Suppose ...
1
vote
0answers
48 views

Using induction to show associativity on $x_1+\dots + x_n$

I want to use induction to show that the sum $x_1 + \dots + x_n$ of real numbers is defined independently of parentheses to specify order of addition. I know how to apply induction(base, assumption, ...
1
vote
0answers
51 views

can anyone prove this with induction?

Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ ...
1
vote
0answers
50 views

Closed form of an equation

How could I find a closed form for the equations 1^3 = 1 , 2^3 = 3 + 5 , 3^3 = 7 + 9 + 11 , 4^3 = 13 + 15 + 17 + 19, 5^3 = 21 + 23 + 25 + 27 + 29 ... and Prove this closed form by induction? Thanks
1
vote
0answers
22 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
1
vote
0answers
15 views

Induction for quantified statement with two discrete parameters

Given a quantified statement ∀n, n>0 (∃x, x>2k | x=2k+n) ( a subset of the natural numbers) This can logically this can be deduced as valid; however, I wish to use induction. Specifically I would ...
1
vote
0answers
14 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
0answers
37 views

Game of writing a binary sequence proof

Let $n \gt 2$ be a natural number. We consider the following game. Two players write a sequence of $0$s and $1$s. They start with an empty line and alternate their moves. In each move, a player writes ...
1
vote
0answers
52 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
1
vote
0answers
28 views

Prove that $10 | (n^a - n^b)$.

$n$ is a positive integer. Prove that there exists positive integers $a$ and $b$, $(a > b)$ such that $10 | (n^a - n^b)$. I have tried to prove this by induction on $n$, but I get stuck at the ...
1
vote
0answers
35 views

RE : Is greatest common divisor of two numbers really their smallest linear combination?

This is in reference to the same proof given in the post Is greatest common divisor of two numbers really their smallest linear combination? I couldn't add a comment there so I'm asking it here. I ...