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
1answer
45 views

Proof by induction on multiple variables

I have the following term to prove by induction: $$ \sum_{i=0}^m C(n,i)\le n^m+1 $$ I know that base case for this is n = 1 and m = 0. However, I am not sure how to proceed from there.
4
votes
0answers
54 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also ...
2
votes
7answers
112 views

Prove $(1+2+…+k)^2 = 1^3 + … + k^3$ using induction [duplicate]

I need to prove that $$(1+2+{...}+k)^2 = 1^3 + {...} + k^3$$ using induction. So the base case holds for $0$ because $0 = 0$ (and also for $1$: $1^2 = 1^3 = 1$) I can't prove it for $k+1$ no matter ...
0
votes
2answers
50 views

prove, using induction that for natural $n$ and $0<x<1$ that $(1-x)^n<\frac{1}{1+nx}$

How to prove, using induction, that for every natural $n$, and for every $0<x<1$ :$$(1-x)^n<\frac{1}{1+nx}$$
-1
votes
7answers
120 views

prove that for every natural n, $5^n - 2^n$, can be divided by 3 [duplicate]

How to prove, using recursion, that for every natural n:$$5^n - 2^n$$ can be divided by 3.
1
vote
1answer
31 views

Analysis sequence convergence

Given: $a_0=4$, $a_{n+1}=\sqrt{2+a_n}$. Show that $(a_n)$ converges and determine the limit. I don't know where to start. I have tried determining the limit: I know that $a_n\to A$, so $a_{n+1}\to ...
2
votes
1answer
39 views

Is there a formula for general induction?

When I read about mathematical induction, there is no general formula, just a notion that is described: Show true for $n = 1$ Assume true for $n = k$ Show true for $n = k + 1$ ...
11
votes
6answers
1k views

Why do we do mathematical induction only for positive whole numbers?

After reading a question made here, I wanted to ask "Why do we do mathematical induction only for positive whole numbers?" I know we usually start our mathematical induction by proving it works for ...
2
votes
1answer
51 views

Induction based on sum of $kth$ powers. [duplicate]

It is showable directly by induction that the following are true: $$\sum k = \frac{1}{2}n(n+1)$$ $$\sum k^2 = \frac{1}{6}n(n+1)(2n+1)$$ $$\sum k^3 = \frac{1}{4}n^2(n+1)^2$$ etc. Now, by doing some ...
1
vote
5answers
72 views

Proof that $2^{2n}-1$ is not prime for $n \in \mathbb{N}, n > 1$

I notice that the number seems to be a multiple of 3: for n=2: $2^4 -1 = 15 $ for n=3: $2^6 -1 = 63$ for n=4: $2^8 -1 = 255$ How do I generalise?
1
vote
2answers
55 views

Let $f(x) = x^n$. Show that $f^{(n)} = n!$ and $f^{(m)} (x) = 0$ for all $m > n$.

I'm supposed to use mathematical induction to solve this Show that $P(1)$ is true Assume $P(K)$ is true Show that $P(K+1)$ is true How do I approach this problem?
1
vote
1answer
43 views

Taylor Series Polynomial Proof using Induction

If $f : \mathbb R \to\mathbb R $ is a polynomial function of degree $n$ with $a \in\mathbb R$. Show that the $n$-th Taylor polynomial $P_{f,a,n}$ of $f$ at $a$ is equal to $f$. I know that I need to ...
1
vote
1answer
29 views

Let $M$ is a squared matrix. Find $M^n,n\in\mathbb{N}$

Let $M=XAX^{-1}$ where $ X= \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix}$, $A= \begin{bmatrix} 1 & 0 \\ 2 & 1 \\ ...
5
votes
0answers
124 views

Sum of like powers equal to a power

It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction ) A generalization of this is also known : $$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} ...
-2
votes
1answer
45 views

Prove n-1*n = ((n-1)*n*(n+1))/3 induction Alegebra confusion

Currently following a tutorial Hypothesis is k-1(k) = (k-1(k)k+1)/3 ...
1
vote
0answers
16 views

Establishing a proof through the structure of a term in predicate logic

Let $F$ be a ranked alphabet of function symbols. And let $X$ be an alphabet of variables. The set of terms $T$ , built over $F$ and $X$ , is inductively defined as follows: If $x\in X$, then ...
1
vote
1answer
49 views

Natural numbers but without induction?

If I recall correctly the Peano axioms of natural numbers includes the axiom that proofs of induction should be valid. I am curious about what properties these "not so natural" numbers could have if ...
3
votes
1answer
38 views

Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3 $ ...
0
votes
0answers
10 views

Proof by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ sentence in a full tree [duplicate]

How do I prove by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ where: $d$ = the number of children of each node; $n$ = the number of leaves; $l$ = the depth of each leaf $l_1, \ldots, l_n$? ...
1
vote
0answers
30 views

Mathematical induction divisibility [duplicate]

I am currently looking through this problem in this video https://www.youtube.com/watch?v=eYy_rXKJDtk The video asks: Prove that 4^k-1 is always a multiple of 3 for n = 1,2,3... Looks like an ...
3
votes
4answers
94 views

Inductive Proof of $n! < n^n$

Looking at the Wikipedia page on Mathematical Induction, I see that $n! < \frac{n^n}{2^n}\; \forall n>6$ I have been trying to prove that $n! < n^n \; \forall n>5$ using induction myself ...
3
votes
2answers
59 views

How to use Mathematical Induction to prove $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1}$?

$$\frac{1}{1 \cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}$$ What I have so far in the induction is: $$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + ...
2
votes
3answers
56 views

Show by induction that $(n^2) + 1 < 2^n$ for intergers $n > 4$

So I know it's true for $n = 5$ and assumed true for some $n = k$ where $k$ is an interger greater than or equal to $5$. for $n = k + 1$ I get into a bit of a kerfuffle. I get down to $(k+1)^2 + 1 ...
1
vote
1answer
17 views

Give a recursive definition for the set T.

I am not sure if math stack exchange is the right place to ask about this but I will ask away. Consider the set T of binary trees that have the following property: For each node in the tree, the ...
0
votes
6answers
48 views

Inductive proof of 2|($n^2$ +3n + 2) if n is a natural number

I was looking at an example problem: Please prove the following statement: if n is a natural number then $\displaystyle2|( n^2 + 3n + 2)$ In the example solution it showed: Proof: P(n) be ...
0
votes
0answers
32 views

Prove $n*2^n \leq 3^n$ using induction [duplicate]

I am trying to prove $n*2^n \leq 3^n$ for all $n \geq 1$ using induction. I tried to get it into the form $(n+1)*2^{n+1} \leq 3^{n+1}$ as follows: $n*2^n \leq 3^n$ $2n*2^n \leq 2*3^n$ $n*2^{n+1} ...
3
votes
3answers
68 views

Proving an inequality using mathematical induction

Using induciton, I have to prove following inequality: $$ 3^n > n2^n $$ I proved it for $n = 0$. Then assuming that the above is true, I try to prove it for $n+1$. So I start with: $$ (n+1)2^{n+1} ...
1
vote
3answers
42 views

How do you select base-cases for this proof?

Let $P(n)$ be the statement that a postage of n cents can be formed using just $4$-cent and $7$-cent stamps. Show by mathematical induction that $P(n)$ is true for $n ≥ 18$. Hint: carefully ...
1
vote
1answer
51 views

Given a polynomial $p$, then $\forall K>0$, $\exists r_k$ such that $|t|\geq r_k \Rightarrow |p(t)|\geq K$

Let $p: \mathbb{R} \rightarrow \mathbb{R}$ be polynomial $p(t) = a_0 + a_1 t+ \cdots + a_n t^n $ $(a_n \neq 0)$. I'd like to prove the following statement by induction: $\forall K>0$ there exists ...
0
votes
3answers
23 views

Prove by induction that $\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m}, \qquad \forall n \in N$

Prove by mathematical inductin that: $$\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m}, \qquad \forall n \in N$$ is true. For $n=1$, ($\frac{1}{2} = \frac{1}{2})$ it holds. But ...
1
vote
1answer
46 views

Prove using the binomial theorem that $(1+\frac{1}{n})^n < \sum_{j=0}^n \frac{1}{j!} < 2 + \frac{1}{2} + \frac{1}{4} + …+ \frac{1}{2^{n-1}}$

I understand how to prove this problem, essentially the middle term $\sum_{j=0}^n \frac{1}{j!}$ is equal to the Euler's number, e, and the third term in this sequence is equal to 3. However, I am not ...
1
vote
1answer
38 views

Show that a set of connectives {∨, ∧} through structural induction is not a complete set of connectives

I understand how a set of connectives such as {∨,∧,¬}, can be considered adequate, but I'm not fully understanding how one would go proving something that is not adequate The full problem is as ...
4
votes
3answers
56 views

Proof of inequality by induction

Prove by induction that $(1-a)^n ≥ 1-na$, $∀ n≥1$ for appropriate $a$. Okay, so I have no problem with this except the requirements on $a$ for this inequality to hold. My lecturer claims we require ...
-3
votes
3answers
49 views

How does $(n+1)! - 1 + (n+1)(n+1)! = (n+1)!(1+n+1) - 1$? [closed]

How does $(n+1)! - 1 + (n+1)(n+1)! = (n+1)!(1+n+1) - 1$? I cannot figure this out, help. This deals with Mathmatical induction problem. I've tried factoring but it doesn't work out.
1
vote
3answers
39 views

evaluating the limit $\lim \limits_{n \to \infty} \frac{(4(n*3^n + 3))^n}{(3^{n+1} (n+1)+3)^{n+1}}$

I'm trying to solve the following limit: $\lim \limits_{n \to \infty} \frac{(4(n3^n + 3))^n}{(3^{n+1} (n+1)+3)^{n+1}}.$ I've got no idea where to even start, it's just too big! I don't know whether ...
1
vote
1answer
36 views

Prove (by induction) that the given closed form indeed gives the same sequence.

Show that the sequence defined by $𝑏_𝑘=𝑏_{𝑘−1}+2𝑘$ for $𝑘≥2$, where $𝑏_1=4$, is equivalently described by the closed formula $𝑏_𝑛=2𝑛+1$. Start by writing first $6$ terms and then you’ll need ...
1
vote
4answers
101 views

How to prove $1 + 3 + 3^2 + … + 3^{n-1} = (3^n - 1)/2$ by mathematical induction?

$1 + 3 + 3^2 + ... + 3^{n-1} = \dfrac{3^n - 1}2$ I am stuck at $\dfrac{3^k - 1}2 + 3^k$ and I'm not sure if I am right or not.
0
votes
1answer
36 views

prove by induction that $F(n) \leq \left(\frac{1 + \sqrt{5}}{2}\right)^n$

I had the following prove by induction problem in an exam and I didn't do it because I didn't know how to. Could anyone solve it, please? $F(0) = 0$ $F(1) = 1$ $F(n) = F(n-1) - F(n-2)$ $F(n) \leq ...
2
votes
1answer
57 views

$1/4 + 1/ 9 + … 1/n^2< 1$ induction

I have been trying this sum for long and do not know how to proceed. Q. Prove using induction that $$\frac1 4 + \frac1 9 + ... + \frac 1 {n^2} < 1$$ A. By induction. Let $$P(n) = \frac1 4 + ...
2
votes
3answers
57 views

Mathematical Induction question: Prove divisibility by $4$ of $5^n + 9^n + 2$

Use mathematical induction to prove that $5^n + 9^n + 2$ is divisible by $4$, where $n$ is a positive integer.
3
votes
2answers
39 views

Prove inequality using binomial theorem

I have this math question that I'm kind of stuck on. Use the binomial theorem to prove that for all integers $n\ge 2$:$$\left (1+\frac{1}{n}\right )^n < \sum_{j=0}^{n}{\frac{1}{j!}} < ...
1
vote
3answers
35 views

Validity of Inductive Proof - Proof Confirmation

I want to prove this statement using weak induction: Every integer $n>11$ is a sum of two composite integers. When I prove it I get stuck at something basic I believe but unclear for me: I ...
3
votes
4answers
114 views

Prove that $\cos\left(\frac{2\pi}{n}\right)+\cos\left(\frac{4\pi}{n}\right)+\ldots+\cos\left(\frac{2(n-1)\pi}{n}\right)=-1$

May you help on how to start, or where to look for the following question? By using the $n$-th roots of the unity, show that: ...
1
vote
1answer
39 views

Proof by induction: Number of subsets of cardinality 2

We would like to prove by induction that the number of the subsets of cardinality $2$ of a finite set with $n$ elements is given by $\frac{n(n-1)}{2}$. I know the reason why this is true, but how ...
-2
votes
1answer
46 views

Show with mathematical induction using n:

If n men and n women meet in order to marry then there are exactly n! different arrangements such that each man is married with exactly one woman and vice versa. Hint: Give numbers to the men and ...
36
votes
15answers
4k views

Is it a new type of induction? (Infinitesimal induction) Is this even true?

Suppose we want to prove Euler's Formula with induction for all positive real numbers. At first this seems baffling, but an idea struck my mind today. Prove: $$e^{ix}=\cos x+i\sin x \ \ \ ...
1
vote
2answers
40 views

Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
4
votes
1answer
62 views

How to calculate $\int_0^1\cdots\int_0^1\frac{1}{x_1+x_2+\cdots+x_n+1}dx_1\cdots dx_n$

I met an integral $$\int_0^1\cdots\int_0^1\frac{1}{x_1+x_2+\cdots+x_n+1}dx_1\cdots dx_n$$ I calculated $n=1,2,3$ and made an induction! then i got the result: ...
0
votes
1answer
29 views

Can someone explain the division in this proof of the sum of harmonic sequence? $(n+1)*h(n) - n$

So... this is the explanation my instructor gives in his PDF, but I can't make heads or tails of it. Use mathematical induction to prove that for all positive integers n: H1 + H2 + . . . + Hn = (n ...
7
votes
5answers
660 views

Math induction problem with large numbers

I am trying to figure out how to prove $17^{200} - 1$ is a multiple of $10$. I am talking simple algebra stuff once everything is set in place. I have to use mathematical induction. I figure I need ...