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
votes
1answer
47 views

Prove the limit using mathematical induction and L'Hospital's rule. [closed]

Prove that for every $c>0$ and for every polynomial $p(x) \in \mathbb{R}[x]$ the limit $\lim\limits_{x \to \infty}{\frac{p(x)}{e^{cx}}}$ exists and is eqaual to $0$. Use the L'Hospital's Rule and ...
2
votes
1answer
31 views

Conjecture for the maximum number of rooms.

The puzzle I have is essentially this, but for $n$ rows.For this instance of $n=5$, quick tallying reveals the answer to be $21$. For $n=4$, it is $13$. For $n=3$, it is $7$. For $n=2$ it is $3$. ...
1
vote
2answers
65 views

Induction and contradiction

I want to prove a statement by induction , I tasted the base case, then I considered the induction hypotesis for n , so I assumed by absurd that is not true for n + 1 but this contradicts the ...
2
votes
0answers
46 views

Knuth algorithm on constructing a proof

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the ...
2
votes
1answer
94 views

Showing that $3^{(3^n - 1)}$ divides $(3^n)!$

I am trying to solve the following by using induction: Show that $3^{(3^n - 1)}$ divides $(3^n)!$ for any non-negative integer $n$. But isn't the question incorrect, since it doesn't hold for ...
1
vote
0answers
37 views

How to correctly set up inductive proofs?

In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence $0, 1, ...
0
votes
0answers
26 views

Prove that every natural number, bigger than 7, can be presented by sum of threes and fives? [duplicate]

How to prove that every natural number, bigger than 7, can be presented as a sum of threes and fives? e.g. $21=5*3+3*2$, $58=5*11+3*1$ etc.
1
vote
2answers
69 views

Prove by induction $ 1 + 3 + 5 … + (2n - 1) = n^2, \forall n\in \Bbb Z $

Prove by induction $ 1 + 3 + 5 ... + (2n - 1) = n^2, \forall n\in \Bbb Z $ (This is the exact question taken from my Discrete Math class final exam, i don't misread anything) I could prove it if it ...
0
votes
0answers
32 views

If I can prove f(n) = g(n+1) by induction when n is finite, Can I prove f(n) = g(n) by taking n = $\infty$

I have to prove f(n) = g(n) when $n = \infty$. Now I can prove f(n) = g(n+1) by induction when n is finite. Can I say $f(n) = g(n)$ by taking $n = \infty$?
1
vote
1answer
109 views

Structural induction on binary trees

I have some problems understanding structural induction, maybe because it is such a rigorous way of thinking, so I don't really know where to start here.. This is taken from our Algorithms course and ...
1
vote
1answer
26 views

Prove that a given CFG grammer $G$ is equivalent to language $L$

I need help to prove that the given CFG grammar $G$ is equivalent to language $L$: as $S\to 0S1 \mid SS \mid \varepsilon$ and $L=\{w\in\{0,1\}^* \mid \#_0(w)=\#_1(w)\text{ and for any prefix } u ...
3
votes
1answer
30 views

How was induction used here?

I was reading the proof of the induction for this question and didn't understand the step where they did $t! > (n^2)^{t-n^2} = n^tn^{t-n^2} > n^t$. How is $n^2$ even related to the problem and ...
1
vote
3answers
87 views

Proof by induction that $5|11^n-6$ for all positive integers $n$

Prove by induction that $5|11^n-6$ for all positive integers $n$ Let $p(n) = 11^n-6.$ We have $p(1) = 5$, thus it holds for $p(1)$. Assume it holds for $p(k)$. We will prove that it's true for ...
4
votes
5answers
236 views

mathematical induction for divisibility: Is this one a valid proof? If so why?

I must prove that $7^n-1$ $(n \in \mathbb{N})$ is divisible by $6$. My "inductive step" is as follows: $7^{n+1}-1 = 7\times 7^n-1 = (6+1)\times 7^n-1 = 6\times 7^n+7^n-1$ So now, $6\times7^n$ is ...
0
votes
0answers
27 views

Proving a feature of p-series sum by induction

Prove by using induction that for all $n,r \in \mathbb{N}$ we have $$\sum_{i=1}^{n}i^r=\dfrac{n^{r+1}}{r+1}+\dfrac{n^r}{2}+P_r(n)$$ And here , $P_r(n)$ is a polynomial which its degree is less than ...
-1
votes
4answers
40 views

Can someone clarify step-by-step how to solve such Recursion & Induction question?

I've a discrete math exam coming up in two weeks and the only thing I've problem with is induction and recursion. I do know how to check the base case of a certain induction i.e. check and compare if ...
0
votes
1answer
46 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
73 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
127 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
50 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
57 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
69 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
39 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
57 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.