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
44 views

Please explain this basic proof

In my freshman math course book there's a proof of associativity of addition on the natural numbers using mathematical induction. The author proves the base case and assumes the hypothesis, $a+(b+c) = ...
0
votes
2answers
33 views

Proving $\prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$ by induction

So I have to prove the following using induction. ${\displaystyle \prod_{i=2}^{i=n} \left(1-\frac{1}{i^2}\right)} = \frac{n+1}{2n}$ I showed the basis step that if $n=i=2$, then the two functions ...
1
vote
0answers
28 views

Prove by induction that this sum is not a natural number. [duplicate]

Prove by induction that $1+\frac{1}{2}+\frac{1}{3} +...+\frac{1}{n}$ for any $1<n$ and $n\in \Bbb{N}$ is not a natural number.
1
vote
0answers
75 views

Proof of the well ordering principle without mathematical induction

Is it possible to prove the well ordering principle without using mathematical induction? If yes, how?
2
votes
1answer
63 views

Proving that $n \leq m^{2} \leq 2n$ by induction

I am trying to prove that there exists a perfect square between a natural number and its double, and I am trying to prove it by induction. Here is my proof so far, but I am kind of stuck. for $n=1$, ...
0
votes
2answers
43 views

Showing that the $n$th derivative of this piecewise function vanishes at $0$

Let $$f(x)= \begin{cases} e^{-1/x} & x>0 \\ 0 & x\le 0 \end{cases} $$ I want to show that $f^{(n)}(0)=0$ for every $n\in\mathbb{N}$. My idea is to do this by induction on $...
0
votes
1answer
104 views

GCD induction proof

I apologize if this is a duplicate question (believe me, I've searched). This question is a part of an ungraded class warm-up exercise. Question: Using induction, prove that for all positive integers ...
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
60 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} b^{k-...
1
vote
2answers
53 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
62 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
60 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) \\ Im((a+ib)...
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
35 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
67 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
69 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
83 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
87 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
74 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
101 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
34 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 case ...
0
votes
1answer
50 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)$ $q(0)=...
1
vote
2answers
41 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 but ...
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
110 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
55 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
81 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, \\ S_{...
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
61 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
58 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 much!...
3
votes
2answers
89 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 \end{align*...
0
votes
2answers
136 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
101 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 I'...
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. $$\begin{pmatrix}2\\2\end{pmatrix}+\begin{pmatrix}3\\2\end{pmatrix}+\begin{pmatrix}4\\2\end{pmatrix}+\cdots+\begin{pmatrix}n\\2\...
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
144 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
95 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 ...