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

0
votes
2answers
173 views

Proving a slight variation of the fibonacci formula using complete induction

I learned this formula for the Fibonacci series, and its respective proof in one of my Computer Science classes. F(0) = 0; F(1) = 1; F(2) = 1 However, I am taking an abstract mathematics class and ...
1
vote
4answers
116 views

Why can't I prove this statement by simple induction? Sum of $1/2^1 + \cdots+ n/2^n = x$

I have to prove the following: $$ \frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}=2-\frac{2 + n}{2^n}. $$ I am trying to prove this by simple induction. First, I proved that $P(1)$ ...
2
votes
2answers
168 views

For every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$.

Use induction to prove that for every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$. I can see that for $n=1$, $ 3^{3} -1=26\cdot 1$. As for inductive step, assuming that the statement ...
1
vote
1answer
65 views

How to justify “two-dimensional” induction

Suppose I have a statement $p(m,n)$ where $m,n \in \mathbb{N}$ that I want to prove. Suppose I have proofs of the following: $p(1,n)$ is true for all $n \in \mathbb{N}$. $p(m,1)$ is true for all $m ...
0
votes
1answer
29 views

Mathematical induction

I've already proven the first part but in (ii) I managed to get until $u_{n+1} = \sqrt{9-\epsilon} - 1$ I don't know how to show the approximation answer.
0
votes
1answer
78 views

Mathematical induction

The sequence of real numbers $a_1, a_2, a_3,...$ is such that $a_1=1$ and $$a_{n+1}=\left(a_n+\frac1{a_n}\right)^\lambda,$$ where $\lambda$ is a constant greater than $1$. Prove by mathematical ...
0
votes
3answers
54 views

Proof by induction

This is a topic I always struggle with. Could someone help me prove this: Prove by induction: $$ \sum_{k=1}^n 2k = n^2 + n, $$ Thanks for any help
1
vote
0answers
72 views

Why this proof is incorrect?

I have an exercise that I cannot really understand: Let $P(n)$ be a property over the naturals (i.e., $n \in N$). The induction axiom, taking $0$ for the base-case instance, is the formula: ...
0
votes
3answers
56 views

Differentiation proof obyinduction

If we have two functions, $a(x)$ and $b(x)$ and those function are differentiable inifitely many times. What is a closed form to $$\frac{d^n}{dx^n} (ab)$$ How can I use induction here? I don't ...
4
votes
1answer
92 views

Proving by induction that $\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + … + n^2$ [duplicate]

Note: I am asking this question as a simple introductory question to proofs by induction, to which I will give also my formal answer (which should be correct, if not, please comment) for future ...
1
vote
1answer
31 views

Prove by induction that $\sum_{\varnothing\ne S\subseteq[n]}(\prod S)^{-1}=n$.

I'm having a hard time visualizing how to prove the following by induction: For every positive integer $n$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $A$ be a set. Use the notation $P(A)$ ...
1
vote
2answers
25 views

Induction of $\sum_{k=1}^{n} (-1)^{n-k}k^2 = \frac{n(n+1)}{2}$

I'm trying to prove following statement through induction: $\sum_{k=1}^{n} (-1)^{n-k}k^2 = \frac{n(n+1)}{2}$ I have only seen how to prove with induction when the variable $n$ is not included in the ...
0
votes
1answer
33 views

How to verify by induction that that the probabilities of all sample points add to unity?

I have this question. An urn contains b black and r red balls. A ball is drawn at random. It is replaced and moreover, c balls of the color drawn and d balls of the opposite color are added. A new ...
6
votes
1answer
569 views

Structural Induction vs Normal (Mathematical) Induction

In computer science and semantics I have come across structural induction many times. In that context, it is often presented as something different from but similar to mathematical induction, ...
0
votes
2answers
104 views

Mathematical induction with binomial coefficients

I am trying to prove the following equation using mathematical induction: $$\sum \binom{n}{k}2^k = 3^n.$$ I am able to prove a similar induction without the $2^k$ on the left side and with $ 2^n $ on ...
1
vote
0answers
24 views

Fibonacci, prove that $F_{n}\cdot F_{n+2}-({F_{n+1}})^2=(-1)^n$ with induction [duplicate]

I need to prove by induction that: $$F_{n}\cdot F_{n+2}-({F_{n+1}})^2=(-1)^n$$ I did the following: Check if the statement holds for $n=1$: $$1\cdot 3-(2)^2=(-1)^1$$ Check if the statement ...
1
vote
1answer
68 views

Confusion on unberstanding the proof of induction regarding Fibonacci numbers

I am trying to understand the proof that "For all $n\geq 2, F_n^2-F_{n+1}F_{n-1}=(-1)^{n-1}$.Where $F_n$ stands for the Fibonacci number at $n$. I got this proof from a book and here is the proof. ...
1
vote
1answer
119 views

$a^n-b^n=(a-b) (\sum_{i=0}^{n-1}a^ib^{n-1-i})$ [duplicate]

How do I use finite induction to prove that $$a^n-b^n=(a-b) (\sum_{i=0}^{n-1}a^ib^{n-1-i}), \forall a,b\in \Bbb{R}\space \text{and} \space \forall n \in \Bbb{N}?$$ Ok, for $n=2$ it's fine. ...
3
votes
0answers
61 views

Verify my induction proof for Balanced Ternary expressions

In first place I apologize if you find a grammatical error, my English is not too good for now, but I'm work on it. That also goes for errors in my question (this is my first post). I encounter the ...
0
votes
2answers
52 views

Mathematical Induction with an inequality

Use mathematical induction to prove that $$1\cdot3+2\cdot4+3\cdot5+...+n(n+2)≥ \frac{1}{3}(n^3+5n)$$ for $n≥1$. I have tried this and got what I thought was the correct answer but it doesn't work for ...
2
votes
3answers
66 views

To prove $x_n<3$ for sequence $x_{n+1} = \frac{12(1+x_n)}{13+x_n}$ by induction

Prove $x_n<3$ for a sequence given by $$x_{n+1} = \frac{12(1+x_{n})}{13+x_{n}}$$ where $x_1$ is positive real number less than $3$. For $n = 1$ statement is trivial, but I am stuck at doing ...
1
vote
1answer
68 views

prove by inductive step [duplicate]

I have some problem to prove this statement by the Principle of mathematical Induction. $$\sum_{i=0}^{n} \binom{n}{i} = 2^n.$$ So I begin with the base step. For $n=0$, $$\sum_{i=0}^{0} \binom{0}{i} ...
1
vote
5answers
80 views

How can I prove this $(1 + x)^n \geq n\cdot x + 1$

A theorem says: $\forall x > -1$ and $\forall n \in \mathbb{N}$: $(1 + x)^n \geq n\cdot x + 1$ Base: $n = 0$ $(1 + x)^0 \geq 0\cdot x + 1$ $1 \geq 1$ [ok] Hypothesis: Suppose $(1 + x)^n ...
3
votes
1answer
165 views

Proving by induction that $a_n = 2^n - 1$, $\forall n \in N$

Note: I am asking this question because I though my solution is interestingly easy and could solve for others with the same problem. If the solution is not completely correct, or incorrect, please ...
0
votes
2answers
54 views

Prove by induction that $\sum^{n}_{k=1}5k-4=\frac12n(5n-3)$ is true for $n\ge 1$

Prove by induction that the following equation is true for $n\ge1$ $$\sum^{n}_{k=1}5k-4=\frac12n(5n-3)$$ I did the following: ...
0
votes
2answers
33 views

$n$ points on a circle connect by lines, the sum of the internal angles is $(n - 1) 180$°

I am trying to understand a proof by induction on a geometry problem: For all $n\geq 3$, if $n$ distinct points on a circle are connected in consecutive order by straight lines, then the ...
1
vote
1answer
89 views

Using induction for sequences defined by recursion, such as $a_{n+1} = \frac14(a_n^2 +3)$

Let the sequence $\{a_n\}$ be defined by $a_{n+1} = \frac14(a_n^2 +3)$. We want to prove that if the first term $a_1$ is between $0$ and $1$ then the sequence converges. My question is why do we ...
5
votes
1answer
148 views

Inequality with sum of Binomial coefficients.

Prove that for every positive integer $n \ge 2$$$\sum^n_{k=1}k \sqrt{\begin{pmatrix}n\\ k\end{pmatrix}}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
3
votes
2answers
217 views

Prove the empty set is a subset of every set. Does induction work?

I've taken a look at the proofs by contrapositive and by vacuous truths (for the above title), but I was wondering whether or not the following proof by induction works. The following proof proceeds ...
4
votes
4answers
67 views

How to proof that $\sum_{i=1}^{2^n} 1/i \ge 1+n/2$

I had troubles trying to prove that for every $n\ge1$ $$\sum_{i=1}^{2^n}\frac1i\ge 1+\frac n2$$ Can you give me a hint about the induction proof or show me in detail how can I prove it? I would ...
2
votes
1answer
37 views

Proving by induction $3^{n-2}\le(n-1)! : \forall n\ge 6$

Prove by induction: $3^{n-2}\le(n-1)! : \forall n\ge 6$ The base case and hypothesis are trivial, we want to show that: $3^{n-1}\le(n)! : \forall n\ge 6$, but I get stuck very early: $3^{n-1}\le ...
3
votes
1answer
58 views

Simplexes in $\mathbb R^n$ have at most $n+1$ points

This is an exercise from the book Espaços Métricos (metric spaces) by Elon Lima. I'm translating it (the part of it that I'm having trouble with): Show that if $X\subset\mathbb R^n$ is such that ...
0
votes
1answer
327 views

strong induction example

There is following example given in a book. I am not sure how do we conclude that $a$ is divisible by prime? See this section: Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and ...
3
votes
3answers
124 views

${n \choose k}\leq n^k$

Let $n$ et $k\in \mathbb{N}$ such that : $k\leq n $ Show that :$${n \choose k}\leq n^{k}$$ My thoughts: note that for all $\ k\leq n$ : $${n \choose k}=\frac{n!}{k!(n-k)!}$$ To prove ...
1
vote
2answers
34 views

Prove by induction that $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$

Prove by induction $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$ Step 1: Show true for n = 0: LHS: $\frac{0}{2^{0}}$ = 0 RHS = $2 - ...
1
vote
1answer
31 views

Prove by induction that $\sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$

Prove by mathematical induction that $\forall n \in \mathbb{N}:~~~~ \sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$ Step 1: Show true for $n = 1$: LHS: $(-1)^{(1+0)} \cdot 0^{2} + (-1)^{(1+1)} ...
1
vote
2answers
202 views

Simplify sum of factorials with mathematical induction

I want to prove with mathematical induction that: $$\sum_{i=1}^n i \cdot i! = (n+1)! - 1$$ So in the first step we define $n = 1$: $$\sum_{i=1}^1 i \cdot i! = 1 \cdot 1! = 1 = 2! - 1$$ In the ...
1
vote
3answers
83 views

Prove that if a set A of natural numbers contains $n_0$ and whenever A contains k it also contains k+1.

Prove that if a set A of natural numbers contains $n_0$ and that whenever A contains k it also contains k+1. Prove that A contains all natural numbers $ \geq n_0 $ This is rather similar to a ...
0
votes
1answer
276 views

Prove Bernoulli inequality if $h>-1$

Qi) Prove Bernoulli's inequality If $h> -1$, then $ (1+h)^n \geq 1+nh$ Qii) why is this Trivial is $h>0 $ Something i have always been lucky with is having a lot of intuition to go on with ...
0
votes
1answer
31 views

Is this inductive proof valid?

Show that $n!>3^n$ for $n \ge 7$ My attempt: Let the statement $P_n$ say that $n!>3^n$. Base Case Let $n=7$, then $P_7$ says that $7! > 3^7 \implies 5040>2187$ Inductive Step Fix $k ...
1
vote
1answer
52 views

induction, recursive function, discrete mathematics

Please help solve following recursive function. How can I solve $n-10$ for $M(99)$ or $M(98)$ if $n>100$ ? : Find $M(99), M(100)$, and $M(98)$ when $$ M(n) = \begin{cases} n-10, & ...
1
vote
1answer
55 views

Write $(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$ using summation or product notation.

Question: Write the following using summation or product notation: $$(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$$ I have got following conversion, however it looks a bit over complicated: ...
4
votes
3answers
214 views

How to prove $\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ [duplicate]

$\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ I have tried both induction and transforming both sides to get equality but no luck I know that $\sum_{k=1}^{n}\binom{n}{k} = 2^{n}-1$ and ...
5
votes
1answer
60 views

Show that $(1+a_1x+\ldots+a_rx^r)^k=1+x+x^{r+1}q(x)$

Fixed $k\ge 1$. Show that for each $r$, you can find $a_1,\cdot\cdot\cdot,a_r\in \mathbb{F}$ such that :$$(1+a_1x+\cdot\cdot\cdot+a_rx^r)^k=1+x+x^{r+1}q(x)$$ where $q(x)$ is a polynomial. Any ...
1
vote
1answer
123 views

Strong induction. What is responsible for basis step?

I have no problems with weak induction. There is a basis step and inductive step. But it seems that basis step is missing in the strong induction. It says that$$(\forall n[ \forall m<n, ...
4
votes
0answers
154 views

Using induction to prove a congruence?

Let $a = 2+\sqrt{3}.$ By analogy to complex numbers let R$(a)$ be $r,$ the non-surd part of $r + s\sqrt{3}.$ I would like to show that a necessary but by no means sufficient condition that ...
6
votes
3answers
173 views

Proving inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + … + + \frac{1}{2^{n}-1} < n$

Prove the inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ... + + \frac{1}{2^{n}-1} < n$ where $n\in\mathbb{N}\backslash\{0,1\}$ My work At first I tried ...
0
votes
1answer
43 views

Proving that $\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}]$

I'm trying to prove that $$\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}\left[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}\right]$$ for $p,n \geq 2$, $p, q \in \mathbb{N}$. I'm trying to use induction ...
0
votes
1answer
114 views

Cauchy convergence criterion for the sequence $x_{n+1}=\frac{x_n+x_{n-1}}{2}$ [closed]

Suppose $x_0$, $x_1$ are arbitrary and a sequence $(x_n)$ be defined by $x_{n+1}=\frac{x_n+x_{n-1}}{2}, n\geq 1.$ I want show, by induction, the following: $x_0\leq x_n\leq x_1,\forall n\geq 1$; ...
26
votes
4answers
2k views

Why is “mathematical induction” called “mathematical”?

One of my whims is that I never write "mathematical induction" but just "induction". We are doing maths, so what is the point about precising? We don't say "Let $f$ be a mathematical function from the ...