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
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 ...
3
votes
4answers
83 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
72 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
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.
-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 ...
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. ...
0
votes
3answers
99 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 - ...
0
votes
1answer
49 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)$ ...
4
votes
2answers
55 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
1answer
109 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.
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
54 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. ...
0
votes
1answer
80 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, \\ ...
26
votes
9answers
6k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
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
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 ...
-3
votes
1answer
98 views

A polynomial of degree $n$ has at most $n$ zeros

Let $p$ be a polynomial of degree $n$. Prove that it has at most n zeros. Use induction and mean value theorem. I don't understand how to do the induction. I used $n=0$ for the base case ...
10
votes
8answers
1k views

Induction without a base case [duplicate]

I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive ...
5
votes
5answers
14k views

Proof that $n^2 < 2^n$

How do I prove the following statement by induction? $$n^2 \lt 2^n$$ $P(n)$ is the statement $n^2 \lt 2^n$ Claim: For all $n \gt k$, where $k$ is any integer, $P(n)$ (since $k$ is any integer, I ...
10
votes
2answers
310 views

Real Induction Over Multiple Variables?

I've seen in several different places* that one can use normal mathematical induction to prove the truth of a statement that relies not on just one variable (say, $x$,) but multiple variables (for ...
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
99 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 ...
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
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 ...
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 ...
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 ...
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})$. ...
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
42 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
164 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
78 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
33 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 ...
2
votes
3answers
73 views

Prove $\frac{(2n)!}{2^nn!}$ is always an integer by induction.

Hey guys so I have this math question. I have to prove that $\frac{(2n)!}{2^nn!}$ is always an integer by induction where $n$ is a positive integer. This is my approach. First I check the initial case ...
0
votes
1answer
135 views

Proving strong induction implies weak induction

I have been given the following (non-predicate form) definitions for the Principle of Mathematical Induction (weak and strong,respectively) as follows: $I$: Let $U\subseteq\mathbb{N}$ with $1\in U$ ...
1
vote
1answer
41 views

Induction with floor limits

I ran into an exercise in a book that asked the following: Prove that $$S(n) = \sum_{\ell=0}^{[n/2]}\binom{n}{2\ell}p^{2\ell}(1-p)^{n-2\ell} = \frac{1+(1-2p)^n}{2},$$ where $[x] =$ the floor ...
2
votes
3answers
97 views

Fibonacci Loop Invariants

I've taking an Algorithms course. This is non-graded homework. The concept of loop invariants are new to me and it's taking some time to sink in. This was my first attempt at a proof of correctness ...
1
vote
1answer
150 views

Palindrome Induction Proof

Consider strings made up only of the characters $0$ and $1$; these are binary strings. A binary palindrome is a palindrome that is also a binary string. (a)Let $f(n)$ be the number of binary ...
5
votes
3answers
132 views

proving $n!>2^n\;\;\forall \;n≥4\;$ by mathematical induction

My teacher proved the following $n!>2^n\;\;\;\forall \;n≥4\;$ in the following way Basis step: $\;\;4!=24>16$ ok Induction hypothesis: $\;\;k!>2^k$ Induction step: ...
0
votes
0answers
38 views

Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\} $". Here is my proof ...
4
votes
2answers
32 views

Induction question

I have to prove that $$P(n):\quad 1^2-2^2+3^2-\dots+(-1)^{n+1}n^2=(-1)^{n+1}T_n$$ where $T_n=1+2+\ldots+n=\frac{n(n+1)}{2}$. I know I have to solve by induction. So, I showed a base case that when ...
1
vote
1answer
36 views

Fibonacci sequence developing [duplicate]

For the sum $$\sum_i^n {n-i \choose i}$$ I evaluate it for $n=1,2,3,4,5$ For $n=1$ we have $$\sum_{i=0}^1 {1-i \choose i} = {1 \choose 0} + {0 \choose 1} = 1 + 0 = 1$$ For $n=2$ we have ...
0
votes
1answer
54 views

Prove by Induction AM-GM

Suppose that $a,b \in \mathbb{R}$ are positive. Prove that: $$\sqrt{ab} \leq \frac{a + b}{2}$$ Note: This inequality is known as the inequality between arithmetic mean, $\frac{a + b}{2}$, and ...
2
votes
1answer
78 views

Even-order derivative of $y = x\sin (x)$

How do I find the general formula for the even-order derivative of $y = x\sin (x)$? I tried using integration by parts and separation followed by mathematical induction, but I failed to obtain the ...
0
votes
1answer
72 views

Prove by induction that if the first car stops, all of them stop [duplicate]

I have to prove this by induction: $n$ cars are travelling down a narrow one-way street. We know that: The distance d between each two cars is the same. The safe breaking distance b is ...
4
votes
3answers
136 views

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} ...