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

17
votes
0answers
406 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)$ ...
9
votes
0answers
373 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 ...
5
votes
0answers
139 views

Sum of like powers equal to a power

It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction ) A generalization of this is also known : $$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} \tau(d)^3$...
4
votes
0answers
61 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also $...
4
votes
0answers
53 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 &= 2A_{n-...
4
votes
0answers
169 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 $...
4
votes
0answers
104 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 \end{...
4
votes
0answers
117 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
109 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 ...
4
votes
0answers
210 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
123 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
51 views

Can you please comment on and check these couple of induction proofs?

So the following statements need to be proved: 1) $(1+a_1)(1+a_2)\cdots(1+a_n)>1+a_1+a_2+\cdots+a_n$ for $a_i>0,(i=1,2,\ldots,n)$ and $n\ge2$ 2) $(1-a_1)(1-a_2)\cdots(1-a_n)<1-(a_1+a_2+\...
3
votes
0answers
39 views

Proof by “continuous induction”

There’s a method of proving inequalities over some interval of real numbers using differentiation. For instance to prove that $x-\log(1+x) \geqslant 0$ whenever $x \geqslant 0$ we can differentiate ...
3
votes
0answers
38 views

Delete some numbers in $x_1+x_2+…+x_n=y_1+y_2+…+y_m<mn$

Let $$x_1+x_2+...+x_n=y_1+y_2+...+y_m<mn,$$ where $x_i,y_i -$ positive integers. Prove that you can delete some terms (but not all) in the equation and equality remains true. My work so ...
3
votes
0answers
40 views

Historical use of k in proof by induction

Does anybody know the history of why the symbol k is used in proof by induction? As an example, in physics the symbol p is used for momentum because Newton called it impetus, and the letters i and m ...
3
votes
0answers
45 views

Complete Graphs as Unions of Paths

Show that for $n \geq 2$ the complete graph $K_n$ is the union of paths of distinct lengths. I have been stuck on this problem for the past couple of days now and would really like to see a solution/...
3
votes
0answers
56 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
3
votes
0answers
51 views

Prove $\binom{n}{k} = 0$ for $n = 0, 1, … , k-1$

It's a homework problem. Prove $\binom{n}{k} = 0$ for $n = 0, 1, ... , k-1$ I think induction needs to be used, I can do $n = 0$ (and $n = 1$ since our teacher likes us to do the first two), but $n =...
3
votes
0answers
53 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
3
votes
0answers
77 views

Proof of Leibniz formula from Laplace expansion

I'm trying to prove Leibniz formula for the determinant using Laplace expansion. Here's my attempt: For a $1 \times 1$ matrix $A = \begin{pmatrix}a_{11}\end{pmatrix}$, define $\det A = a_{11}$. For ...
3
votes
0answers
63 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
83 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)! \frac{x^{\...
3
votes
0answers
128 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
643 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 ...
3
votes
0answers
247 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 $f(n)=n$ ...
2
votes
0answers
61 views

Determinant of a block matrix $2n$ by $2n$

Consider the block $2n \times 2n$ matrix $$\begin{bmatrix} A&B\\ 0&D \end{bmatrix}$$ where $A,B,D$ are $n \times n$ blocks. Show that $$\det\begin{bmatrix} A&B\\ 0&D \...
2
votes
0answers
32 views

Suppose that $a, b ∈ N$ are relatively prime. Prove that, for any $k ∈ N$, $a^k$ and $b$ are relatively prime.

Note: I've asked this question before, but this one offers a proposed solution and I'm checking for verification. $a$ and $b$ are relatively prime if the greatest common divisor of them is $1$. I am ...
2
votes
0answers
45 views

Binomial Theorem Proof by Induction

Did i prove the Binomial Theorem correctly? I got a feeling I did, but need another set of eyes to look over my work. Not really much of a question, sorry.
2
votes
0answers
34 views

Pascal's triangle induction proof

I am trying to prove $$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$ for each $k \in \{1,...,n\}$ by induction. My professor gave us a hint for the inductive step to use the following four equations:...
2
votes
0answers
46 views

Proof by induction with polynomials

I need to prove by induction the following equality. I did the inductive hypothesis part, but I don't get it when $n=1$. Any help/ hints are greatly appreciated. Be $x\neq 1$ and a real number, prove ...
2
votes
0answers
33 views

Induction on Binary Trees

I am trying to show that $\sum_{i=1}^{M} 2^{-di} \leq 1 $ for a Binary Tree with $M$ leaves each with a depth of $d_i$. I understand intuitively why this is the case, as every subtree at level d, ...
2
votes
0answers
47 views

Proof by Induction that relates to the Jacobian Determinant

Define $f_2$ : $ℝ$ $\to$ $ℝ^2$ by putting $$f_2 (\theta)=(\cos(\theta),\sin(\theta)),$$ and for n $\ge3$ define $f_n: ℝ^{n-1}\toℝ^n$ inductively by setting $$f_n=(\theta_1, \theta_2,\dots,\theta_{n-1})...
2
votes
0answers
99 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
2
votes
0answers
77 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
50 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}$, ...
2
votes
0answers
25 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) = e^...
2
votes
0answers
32 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
97 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
112 views

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

I am looking at the following exercise: Show with induction, that the $i^{\rm th}$ Fibonacci number satisfies the equality: $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
2
votes
0answers
243 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
52 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
2
votes
0answers
96 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
107 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
145 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
68 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
120 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
79 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 $\mathbb{A}...
2
votes
0answers
75 views

monotonicity proof - double induction

Suppose we have 4 functions depending on a variable $x$ : $a(x), b(x), c(x)$ and $d(x)$. I want to prove that $a(x) - c(x)$ is monotonically increasing in $x$, by an induction argument. Also I want ...
2
votes
0answers
224 views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall z\bigr((...
2
votes
0answers
339 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 ...