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

learn more… | top users | synonyms

3
votes
3answers
51 views

Mathematical induction involving inequalities and congruences

I have the following two problems: "Prove each of the following statements by induction for all positive integers $n$:" $2\cdot7^n \equiv 2^n\cdot(2+5n) \bmod 25 \quad$ <-- I have been going at ...
3
votes
1answer
60 views

Induction proof about entries of powers of strictly upper triangular matrix

Let $A$ be a $n \times n$ strictly upper triangular matrix. Prove that, for $k \ge1$, the matrix $A^k$ has the property that $(A^k)_{i,j} = 0$ for all $(i,j)$ with $j-i < k$. Also, show that $A^n ...
2
votes
4answers
74 views

Proving that the series 1 + … + $1 / \sqrt{x}$ < $2 \sqrt{x}$

Proving that the series 1 + ... + $1 / \sqrt{x}$ < $2 \sqrt{x}$ I am doing it by simple induction adding $1/\sqrt{x+1}$ to both sides, but I can't find a way to manipulate this expression and find ...
2
votes
2answers
71 views

Proving by induction that any two natural numbers are equal.

This is something I've been working on for a while now; although it seems trivial, I am confused. I can't seem to find the error. Originally I thought the problem was with the base case, then I ...
-4
votes
1answer
32 views

What is the solution of this calculation?

I just need a fast hint/solution/etc.. $(-1)^{n-1}(n-1)+n+1$ How do I solve this calculation ? Do I multiplicate it out ? $(-1)^{n-1}(n-1)$ comes before $+ n + 1$ But how do I solve this one ? if it ...
0
votes
2answers
28 views

Mathematical induction (prove divisibility)

My attempt at the solution is to let P(n) be $10^{3n} + 13^{n+1}$ P(1)= $10^3 + 13^2 = 1169$ Thus P(1) is true. Suppose P(k) is true for all $k \in N$ $\Rightarrow P(k) = 10^{3k} + 13^{k+1} = ...
0
votes
2answers
40 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 ...
0
votes
4answers
97 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)$ ...
1
vote
2answers
11 views

this is an induction question and the substitution is in the power term

Use induction to prove that for every natural number,n, ((3exp3n) - 1) is divisible by 26. yes i can see for n=1, (3exp3*1)-1=26*1 and n=k (3exp3k)-1= 26k and for n=k+1 (3exp(3(k+1)))-1=26(k+1) but ...
1
vote
1answer
39 views

How to proove the following general form of proof

Suppose I have a statement $p(m,n)$ where $m,n \in \mathbb{N}$ that I want to proove. Suppose I have proofs of the following: $p(1,n)$ true for all $n \in \mathbb{N}$. $p(m,1)$ true for all $m \in ...
0
votes
1answer
25 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
64 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
39 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
0
votes
3answers
50 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 ...
0
votes
0answers
11 views

m-th Dertivative hermitian for even m, and antihermitian for odd m

How to show that the $\left(\frac{d}{dx}\right)^m$ operator, is anti-hermitian for odd $m$ and hermitian for even $m$. I can use mathematical induction to show this, but I need a more formal proof.
4
votes
1answer
44 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
24 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)$ ...
0
votes
1answer
39 views

Formal Method for Determining the Domain of Solutions to an Equation?

     I'm doing an algebra review packet in order to prepare to take an independent-study calculus class. About five eighths of the way through the problems posed by this ...
1
vote
2answers
23 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
27 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 ...
5
votes
1answer
73 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
43 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
21 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
38 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
48 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
35 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
42 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 ...
1
vote
3answers
53 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
5answers
70 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
54 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
39 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
24 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
64 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
80 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
37 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 ...
5
votes
4answers
66 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
36 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
41 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
56 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
100 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
28 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
26 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
51 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
45 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
43 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
30 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
44 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
50 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: ...
3
votes
3answers
51 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
0answers
43 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 ...