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

408 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:...
47 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

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) = ... 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 ... 0answers 244 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 ... 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. ... 0answers 97 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 \... 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). ... 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 ... 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 \...
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 ...