# Tagged Questions

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

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)$ ...
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 ...
139 views

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 ...
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.
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:...
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 ...
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, ...
47 views

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

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