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

1
vote
2answers
77 views

Prove $\frac{1\cdot 3\cdot 5\cdots (2n - 1)}{ 2^n(n + 1)!}\cdot 4^n= \frac{1}{n+1} {2n\choose n}$

Prove: $$ \frac{1\times 3\times 5\times \cdots \times (2n - 1)}{2^n (n + 1)!} \times 4^n = \frac{1}{n+1} \binom{2n}{n} $$ -Sorry I don't know how to do choose notation in stack exchange. I'm ...
0
votes
2answers
56 views

Proving $a^n-b^n=(a-b)\sum_{k=1}^{n}a^{n-k} b^{k-1}$ with induction [duplicate]

How can I prove this using induction. I proved for n=1 but now I'm feeling confused while I'm trying to prove for n+1 because of how the summation develops $$ a^n-b^n=(a-b)\sum_{k=1}^{n}a^{n-k} ...
1
vote
2answers
49 views

Proving $n! > n^2$ by mathematical induction [duplicate]

I'm trying to prove that $n! > n^2$ for $n\geq 4$ by use of mathematical induction, but I get to the inductive step and get lost. But I'm struggling with the inductive step as expected.
1
vote
4answers
61 views

Why proof by induction is working. [duplicate]

I know how to make proofs by induction, but I don't understand why it prove that the propriety is true. It's in fact logical, but how to prove that proof by induction really prove the assertion.
0
votes
3answers
59 views

Show $ \begin{bmatrix} a & -b \\ b & a \end{bmatrix}^k = \begin{bmatrix} Re((a+ib)^k) & -Im((a+ib)^k) \\ Im((a+ib)^k) & Re((a+ib)^k) \end{bmatrix}$

Let $A = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}$ Claim: $A^k = \begin{bmatrix} a & -b \\ b & a \end{bmatrix}^k = \begin{bmatrix} Re((a+ib)^k) & -Im((a+ib)^k) \\ ...
0
votes
2answers
36 views

problem proof of induction $2\cdot3^0+2\cdot3^1+2\cdot3^2+…+2\cdot3^{n-1}=3^n-1$

I need to prove that $2\cdot3^0+2\cdot3^1+2\cdot3^2+...+2\cdot3^{n-1}=3^n-1,\, n=1,2,3,4...$ I know when n = 1 the left side $=2\cdot3^{1-1}=2$. The right side is $2^n - 1=2^1 - 1 = 1$. Thus the ...
0
votes
0answers
34 views

How to prove this equation I have come across by Induction?

I came across this equation in a programming contest(I have simplified it a lot): So the problem directly is we are given some constants < $a_1$ , $a_2$ .. . . . $a_n$ > and we need to ...
1
vote
2answers
56 views

Proving $2^{n+1} < n^2 + 2$ for $n\geq 0$ by induction

I'm trying to prove that $2^{n+1} < n^2 + 2$ for $n \ge 0$ by use of mathematical induction, but I get to the inductive step and get lost. I don't know how to link my assumption to the proof.
0
votes
1answer
25 views

Proof by Induction Using Fibonacci — Not Sure About Other Question's Answers

Here was my previous question: Proof by Induction Using Fibonacci numbers There was a similar one in existence already over here: Inductive proof of a formula for Fibonacci numbers The one that was ...
0
votes
0answers
31 views

Proof by Induction Using Fibonacci numbers [duplicate]

I've seen quite a few of these lying around, but none of them seem to have the specific question I'm looking for. The question is: The Fibonacci numbers $F_0, F_1, F_2, ...$ are defined by: $F_0 = ...
0
votes
1answer
17 views

A proof by strong induction for a recurrences defining function

Problem: Consider the following recurrences defining function, $$f_2(n) = \lbrace 1\ if\ n = 0;\ 1 + \sum_{i=0}^{n-1} f_2(i)\ if\ n > 0\rbrace, f_2: N \to N $$ Prove $f_2(n) = 2^n$ My ...
0
votes
1answer
52 views

Induction proof of sentence [closed]

How do I prove that $\prod\limits_{i=1}^{n} (\frac{2i - 1}{2i}) \le \frac{1}{\sqrt{3n + 1}} $ using induction for n > 0 ? In general, for (n+1) case, I split the productory in: ...
0
votes
1answer
58 views

CNF formula induction proof

I am trying to prove the following theorem: Every proposition formula is logically equivalent to a formula in CNF. As a hint, they say that this can by proven by an induction on the structure of the ...
-1
votes
2answers
61 views

Prove that $\gcd(g_a,g_b) = 1$ given that for $n \in Z^{\geq 0}$, define $g_n = 2^{2^n} + 1$ [duplicate]

Prove that $\gcd(g_a,g_b) = 1$ given that for $n \in Z^{\geq 0}$, define $g_n = 2^{2^n} + 1$. I have already proved that $g_0\cdot g_1\cdots g_{n-1} = g_n -2$ if this hint is useful in this proof.
0
votes
3answers
80 views

Proving $\sum_{i=1}^ni(i+1)=n(n+1)(n+2)/3$ for $n\geq 1$ by induction

I'm trying to prove this by induction: $$1*2 + 2*3 + 3*4 + \cdots + n(n+1) = (n(n+1)(n+2))/3.$$ I have done this so far: Base Case: $n = 1$, works for both. Induction Hypothesis: Let $n = k$, ...
3
votes
4answers
77 views

Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$

Basis step has already been completed. I've started off with the inductive step as just $n=k+1$, trying to involve $f(k)$ into it so that the left over parts can be deducible to be divisible by $x^2$ ...
2
votes
1answer
66 views

Prove by induction area of koch snowflake

For all $n>=0$ prove that the area of a Koch snowflake is $a_n = a_0(\frac{8}{5}-\frac{3}{5}(\frac{4}{9})^n)$ where $a_0=\frac{\sqrt{3}}{4}$ I'm trying to get $P(n+1)$ from $P(n)$ but I'm not sure ...
0
votes
3answers
96 views

the sequence of Fibonacci numbers is defined as follows: $x_1=1, x_2=1$ [duplicate]

the sequence of Fibonacci numbers is defined as follows: $x_1=1, x_2=1$, and, for $n>2, x_n=x_{n-1} + x_{n-2}$. Prove that $$ x_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^n - ...
2
votes
4answers
327 views

Proof that $3^c + 7^c - 2$ by induction

I'm trying to prove the for every $c \in \mathbb{N}$, $3^c + 7^c - 2$ is a multiple of $8$. $\mathbb{N} = \{1,2,3,\ldots\}$ Base case: $c = 1$ $(3^1 + 7^1 - 2) = 8$ Base case is true. Now assume ...
-1
votes
1answer
33 views

For $n \in Z^{\geq 0}$, define $g_n = 2^{2^n} + 1$. Show that $g_0\cdot g_1\cdots g_{n-1} = g_n -2$. [duplicate]

For $n \in Z^{\geq 0}$, define $g_n = 2^{2^n} + 1$. Show that $g_0\cdot g_1\cdots g_{n-1} = g_n -2$ for all $n \in Z^+$. I thought that this could be proved using induction, but then the base ...
0
votes
1answer
48 views

Trouble with induction on polynomials

Use induction to prove the following: $1a)$ Show for all positive integers $n$ that $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$ $1b)$ Show that if $p$ and $q$ are polynomials so that $i)$ ...
1
vote
2answers
40 views

Proving that $\sum_{i=1}^n\frac{1}{i^2}=2-\frac{1}{n}$ for $n>1$ by induction

Prove by induction that $1 + \frac {1}{4} + \frac {1}{9} + ... +\frac {1}{n^2} < 2 - \frac{1}{n}$ for all $n>1$ I got up to using the inductive hypothesis to prove that $P(n+1)$ is true ...
0
votes
0answers
81 views

Waiting times independence and distribution

I am struggling with that: We have irreducible and aperodic Markov Chain on finite state space. There is a state $\alpha$ which is recurrent. We define $\tau_n = \min (m >{\tau_{n-1} : X_m = ...
1
vote
1answer
108 views

Determine the matrix for every n,$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$.

$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$ Is the a formula which give us the matrix for every n? I should make a proof with induction.
0
votes
1answer
53 views

Proof by Induction: "In a Zoo there are$\ k$ monkeys and$\ k$ monkey bars …

I'm struggling hard to prove the following statement/riddle by induction, it is given in the current assignement as a challenge. I really want to understand how to exactly approach such excersises. ...
1
vote
1answer
29 views

Question about structural induction and predecessor relation

I have two questions, about structural induction and the predecessor relation. Why can't a relation be well-founded if it has an infinite descending chain, provided that it has a maximum element? How ...
0
votes
1answer
78 views

Prove this complex inequality by mathematical induction [closed]

Define a sequence of numbers $S_n$ (for integers $n\ge0$) recursively as follows: $$S_n=\left\{\begin{array}{ll} 1& \text{ if }n = 0, \\ 2& \text{ if }n = 1, \\ 3& \text{ if }n = 2, \\ ...
0
votes
1answer
90 views

Let $g_n= {2^2}^n +1 $. Prove $g_0 · g_1 · · · g_{n−1} = g_{n} − 2$

Let $g_n= {2^2}^n +1 $. Prove $g_0 · g_1 · · · g_{n−1} = g_{n} − 2$. I'm not sure how to start this proof, if it should be done algebraically or if I should try to use a proof by induction.
0
votes
1answer
58 views

Definition by Recursion - Need for Rigour

Suppose you define the factorial $n!$ by \begin{align} \tag{1}0!&:=1,\\ \tag{2}(n+1)!&:=(n+1)n!. \end{align} Consider the following argument showing that $n!$ is a uniquely defined function. ...
4
votes
2answers
53 views

Calculating number of tile sequences

My daughter (aged 12) came to me with the problem below. I was able to help her to some extent but I could not see an age-appropriate solution. That is, I could imagine solutions involving factorials ...
1
vote
2answers
28 views

Question Proof By Induction (One Step)

I'm self studying proof by induction and have a question about this one step for this question. I have attached the solution and question below. How does one know that $kx^2\ge0$ ? Thank you so ...
3
votes
2answers
82 views

Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

Prove the summation: $$\sum_{i=1}^n i! \cdot i = (n+1)! - 1$$ using induction. base case: $n=1$: \begin{align*} \sum_{i=1}^1 i! \cdot i &= (1+1)! - 1 \\ 1 &= 2 - 1 \\ 1 &= 1 ...
0
votes
2answers
128 views

Using induction to prove that the infinite set of polynomials is countably infinite

Let $P_n$ be the set of all polynomials of degree n with integer coefficients. Prove that $P_n$ is countable. So I know to prove that $P_n$ is countable, it must be either infinitely countable or ...
0
votes
3answers
48 views

Proof by induction the following: $n+1 ≤ 2^n ≤ (n+1)!$

I've done the basis step for $n=1$ and managed to arrange the $n=k+1$ to: $(k+1) + 1 ≤ 2\cdot2^k ≤ (k+1)!(k+2)$ Not sure how to proceed from here?
5
votes
1answer
98 views

How to show $p_n < p_1 + p_2 + \cdots + p_{n-1}$?

How do you show that, if $p_n$ denotes the $n$th prime, $n > 3$, then $$p_n < p_1 + p_2 +\cdots + p_{n-1}$$ using the Bertrand conjecture and induction? Here is what I've come up with, but ...
0
votes
0answers
26 views

is the Root of a binary Tree counted as a node

I am working on this Homework questions and there's one thing I can't seem to understand. We are trying to proof using structural induction that some elements in T hold for the following statement ...
2
votes
2answers
51 views

Prove that using induction that $\binom22+\dots+\binom n2 = \binom{n+1}2$ [duplicate]

so I have this math problem where I have to prove this using induction. ...
2
votes
2answers
43 views

prove by contradiction:gcd and divisibility

Let's say there are $3$ natural numbers $a,b$ and $c$. $a|(b+c)$ and $\text{gcd}(b,c) = 1$,prove that $\text{gcd}(a,b)=1$ I know that I can prove this statement by contradiction. Let's suppose ...
0
votes
1answer
44 views

How would one go about solving these types of problems?

I'm totally lost. All I know is it has to do with binary trees and may need to be solved using induction. Show that every 2-tree with $n$ internal nodes has $n + 1$ external nodes. Show that the ...
0
votes
3answers
141 views

Prove the inequality for all natural numbers n using induction

$\log_2 n<n$ I know how to prove the base case Base Case $\log_2 1<1$ likewise assuming the inequality for n=k; $\log_2 k<k$ Then to prove by induction I show $\log_2 k<(k+1)$? I know ...
2
votes
1answer
37 views

prove by induction $(1+a)^{1/n} \leq 1+a/n$ while $a\geq-1$

So, I've tried to solve this by induction, but without success. I get this equation: $(1+a)^{1/k}\leq 1+a/k$ and this equation, that I have to prove: $(1+a)^{1/(k+1)}\leq1+a/(k+1)$ I tried ...
0
votes
1answer
28 views

Induction proof with numerator and denominator

I am stuck during the induction process where everything will fall into place if I show: $\frac{x+1}{1-mx} \leq \frac{1}{1 - (m+1)x}$ for any $m \in \mathbb{N}$ and any $x \in (0, \frac{1}{m+1})$. ...
3
votes
4answers
94 views

Prove that $2^n>n^4$ for all $n\geq 17$

I'm always a bit fuzzy on how to solve induction problems involving inequalities. I've managed to get somewhere though, but it looks like I have to go down four levels of induction to prove. This is ...
1
vote
0answers
27 views

Direct proof of the existence of Strong Induction using the Well Ordering Principle

I'm asked to Deduce the alternate form of PMI from WO as a homework problem. To me, this sounds as if I should be doing some form of direct proof of its existence, however, every proof I see that the ...
0
votes
0answers
40 views

Simple induction when dealing with floor

NOTE: This MUST be done with simple induction I'm currently stuck on properly proving induction on a set when floor is involved. I have made up a question to illustrate the issue, it may not be a ...
4
votes
1answer
41 views

Induction over the natural numbers

I need to prove, by induction, that for all $n$ there exists an $m$ with the property that $$m^2 \leq n \leq (m+1)^2$$ I can easily establish a base case (picking $n = m = 0$). I am finding it harder ...
0
votes
1answer
157 views

prove by induction that $\sum_{k=0}^n {n \choose k} = 2^n$ [duplicate]

I have proved previously that $\sum_{k=0}^n {n \choose k} = 2^n$ by using the binomial theorem. I was wondering, however if it were possible to solve this using a proof of induction.
0
votes
1answer
36 views

$P(0), P(1)$ hold and $P(n) → P(n + 2)$ for $n\geq 1$. For which $n$ is $P(n)$ T?

The question is: $P(0)$ hold $P(1)$ hold $P(n) \rightarrow P(n + 2)$ for $n \geq 1$ For which values of $n$ does $P(n)$ hold? My initial answer was that $P(n)$ holds for all odd positive ...
0
votes
3answers
76 views

Does $ \sum_{k=0}^n k {n \choose k}$ have a convenient exponential equivalent? [duplicate]

I know that: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ Does $$0 {n \choose 0} + 1 {n \choose 1} + ... + n {n \choose n} = ??$$ have some convenient simplification?
1
vote
2answers
32 views

Proof by induction: $(1+\alpha)^n\ge 1+n\alpha > +\frac{n(n-1)}{2}\alpha ^2$

so I have this problem. It asks me to prove an expression by induction. Let $n$ be a positive integer, and $\alpha$ any nonnegative real number. Prove by induction that$$(1+\alpha)^n\ge ...