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

Prove that $(n!)^ 2 \gt n^n$ [duplicate]

Prove the above by by mathematical induction By any other method. I was just asked to prove this so I thought of using mathematical induction. My effort : I started first by verification and ...
1
vote
1answer
42 views

help with understanding a proof

again I'm stuck already on the first steps of an inductive proof of $$ (a+b)^{n+1} = \sum_{k=0}^{n+1} {n+1\choose k}a^kb^{n+1-k} $$ that is, I'm trying to understand the solution to this. It starts ...
2
votes
3answers
54 views

Given the sequence $a_0=1, a_1=2, a_2=3, a_n=a_{n-1}+a_{n-2}+a_{n-3}$, prove by strong induction that for $n\geq 0, a_n \leq 2^n$

I've been trying to work this out for some time and I keep getting stuck. Here is what I have thus far: Base Case: $n=0 ; 1 \leq 1$ $n=1 ; 2 \leq 2$ $n=2 ; 3 \leq 4$ Induction hypothesis: ...
2
votes
1answer
85 views

Strong induction on a summation of recursive functions (Catalan numbers)

I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction: $$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$ Some cases: S(0) ...
1
vote
1answer
55 views

How to write a general proof to prove that for all $m$, $m^n \geq n^m$

After proving $m^n \geq n^m$ for several values of $m$, it can be inferred that for every $m$ there's a $k$ such that if $n \geq k$, $m^n \geq n^m$. In other words, this can be generalized as: For ...
2
votes
5answers
136 views

How would you prove inequality $2^n \gt n^{10}$ using induction

For the base case I can put a number such as $100$ for $n$ so $2^{100}\gt 100^{10}$. Ok so now the induction hyp: $2^{n+1} > (n+1)^{10}$ for $n \gt 101.$ where do I go from here? Also do I have ...
2
votes
2answers
180 views

can any identity involving integers be proved by mathematical induction

Hello mathematics community, Today I was studying mathematical induction which is an axiom. I was wondering Can "ANY" identity or inequality involving integers which is already proven can also be ...
2
votes
2answers
65 views

I need to prove that $Z^{n}=r^{n}(\cos n\theta +i\sin n\theta)$ is true by Induction. Can someone confirm whether I have done it right or not?

The equation $$Z^{n}=r^{n}(\cos(n\theta) +i\sin(n\theta))\space\space\space\space\space\space\space\space (1)$$ has to be proved by induction. It is given that $$Z=r(\cos(\theta) ...
3
votes
3answers
92 views

Proof of Equation by Well Ordering Principle

I have an assignment question Prove by either the Well Ordering Principle or induction that for all nonnegative integers $n$: $$\sum_{k=0}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2.$$ I am able to ...
0
votes
1answer
30 views

Extending a theorem true over the integers to reals and complex numbers

How does one generally extend a theorem proved over the integers to the real numbers and beyond e.g. induction proofs, De Moivre's Theorem? I am aware that to extend a theorem proved over ...
0
votes
3answers
48 views

Prove by induction for every integer$\; n\ge 5$, $2^n\gt n^2$.

Prove by induction for every integer$ \;n\ge 5$, $2^n\gt n^2$. My try: $$p(n):\;2^n>n^2$$ verify $P(5)$ $$ p(5):\;2^5>5^2 = 32 > 25 $$ Of course the trick is in the induction step and ...
1
vote
1answer
19 views

Sequence problem by Strong induction

Problem is as follows: Let $X_0 = 3$ and let $X_{n+1} = X_n + \cdots + x_1 + x_0 + 3$ for $n ≥ 0$. Show that $3|X_n$ for all $n ≥ 0$. I have the base case where $n=0$. Therefore $X_0=3$ and $3|0$. ...
0
votes
2answers
221 views

Use mathematical induction to prove Σ n,k=1 (1/k(k+1)) = (n/n+1) for all n in Natural numbers?

This is how far I can get: p(n): nΣk=1 (1/k(k+1)) = (n/n+1) p(1): 1Σk=1 (1/(1+1)) = (1/1+1) => 1/2 = 1/2 p(1) is true. Assume that p(k) is true. p(k) = kΣk=1, (1/k(k+1)) = k/k+1 Show ...
1
vote
5answers
95 views

Proving $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ [duplicate]

I'm trying to prove by MI. I have already distributed n+1, but now I'm stuck on how I can show 9 divides the RHS since $42n$ and $3n^3$ does not divide evenly. ...
1
vote
2answers
270 views

How to solve the recurrence relation for tight asymptotic bound without using master theorem?

I have the following recurrence in my problem: $$T(n)= 4T(n/2)+n.$$ I have solved it by substitution by assuming the upper bound $O(n^3)$ but in solving it for $O(n^2)$ i am having some problems.I ...
0
votes
3answers
59 views

Is my arithmetical proof using induction correct?

The exercise 2.b of my textbook ask me to prove that: $$\text{(P): }\;\forall n\in \mathbb{N}, 13\;|\;(3^{n+2}+4^{2\cdot n+1})$$ I would like to know if my proof is correct and if not what I need to ...
-1
votes
0answers
21 views

Prove that (√ 2)^(log(n)) + log^2(n) + n^10 = O(2^n) [duplicate]

This example question has me rather stumped. I'm not sure where to even start with the log(n) terms. The only clue it gives is "There is at least one non-trivial induction to do as part of the ...
0
votes
3answers
121 views

Proving that the square root of 5 is irrational

Prove that $\sqrt{5}$ is irrational. I begin with the identity $(\sqrt{5} + 2 )(\sqrt{5} - 2 ) = 1$. Then I am told to extract $\sqrt{5}$ from the first or second factor and consider it to be ...
0
votes
1answer
17 views

Proving a statement with two variables by complete induction

I was recently introduced to this topic and I'm trying to prove Tue following statement. For most of numbers, m^n => n^m So I derived this into something that could be proved by induction... The ...
0
votes
2answers
44 views

prove $S(n) \leq (5/2)^n$

I've been flipping through my math book for nearly 5 hours working on these recursive problems and it's just not clicking. I have a recusrive sequence $S(0) =1$ $S(1)=2$ $S(n) = 2S(n-1) +S(n-2)$ ...
0
votes
1answer
51 views

Combinatorial Proof: How many length-n lists can we form using the elements in {1,2,3} [PROOF]

I'm trying to prove that $2\times(3^0) + 2\times(3^1) + 2\times(3^2) + \cdots+ 2\times(3^(n-1)) = 3^n - 1$ by answering the question "how many length-n lists can we form using the elements in ...
0
votes
1answer
26 views

Proving the correctness of a program

So I have this program below SquareRootRecursion that I need to prove is correct. However i'm not sure what it's pre and post conditions would be and how I would use those to prove it's correctness. ...
1
vote
2answers
66 views

Understanding $3^n < n!$

In my class, we are given the answer to this proof. I understand how the inequality was simplified, but don't understand why the bolded statement is true for $k+1,$ or more simply, how that proves by ...
12
votes
5answers
240 views

Show that $({\sqrt{2}\!+\!1})^{1/n} \!+ ({\sqrt{2}\!-\!1})^{1/n}\!\not\in\mathbb Q$

How could we prove that for every positive integer $n$, the number $$({\sqrt{2}+1})^{1/n} + ({\sqrt{2}-1})^{1/n}$$ is irrational? I think it could be done inductively from a more general ...
0
votes
2answers
62 views

Trouble with Fibonacci number mathematical induction

The problem is: $$F_n \leqslant 2F_{n-1}\quad\text{for every integer} \quad n \geqslant 2.$$ I got the smallest case, I just don't know how to get the assumption and the rest of it
2
votes
1answer
69 views

Can't do this induction proof with sqrt(4) repeating

Ok so I realize that the last term will be sqrt(6) but I just don't know how to manipulate this expressions to make it provable by induction. I tried rewriting it using exponents but had no luck ...
0
votes
1answer
52 views

Find all natural numbers n such that n^2 < 2^n

Using induction proof, find all the natural numbers $n$ such that $n^2 < 2^n$. I know that $n$ does not work for $2, 3$, and $4$ but it does work for $0$ and $1$ as well as any number greater than ...
2
votes
1answer
66 views

Proving terms are rational using Mathematical Induction

I was able to do the first part of the question, in the second part (Proof by Induction), I showed it holds for $n=1$: Then I Assumed its true for $n=k$. ...
0
votes
0answers
43 views

Proof using complete induction

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3,2) \in S$ (basis) • If $(x,y) \in S$, then $(3x−2y,x) \in S$ (recursive ...
1
vote
1answer
38 views

Is there a proof for what I describe as the “recursive process of mathematical induction for testing divisibility”.

I was working on my homework for Discrete Math, and we were asked to "Prove: $6 | n^{3}+5n$,where $n\in \mathbb{N}$" my solution varied significantly from how I have seen it done by others. I noticed ...
0
votes
1answer
223 views

Use induction to prove that a function is not one to one

Suppose that m and n are positive integers with m > n and f is a function from $\{1, 2,\ldots, m\}$ to $\{1, 2, \ldots , n\}$. Use mathematical induction on the variable n to show that f is not ...
1
vote
2answers
74 views

Prove $1(1!)+\dots+n(n!) = (n+1)!-1$ using induction

So I'm trying to prove this statement (through induction): $$1(1!)+2(2!)+\dots +n(n!)=(n+1)!-1$$ But I'm confused with the inductive step here: $$(n+1)!-1+[(n+1)(n+1)!] = (n+2)!-1$$ What do I do ...
-1
votes
0answers
25 views

Inductive on the length of $u$ [duplicate]

Prove by inductive on the length of $u$, that $(u^{R})^{R} = u$ "where $R$ indicates reversal" I know the Basis step and Hypothesis step However, could someone help me in inductive step thanks
0
votes
1answer
56 views

Use complete induction to prove the following

Let $f:\Bbb N\to\Bbb N$ be given by $$f(n) = \begin{cases} 3, & n = 1 \\ 1, & n = 2 \\ 2f(n-1)+f(n-2), & n \ge 3 \end{cases}$$ prove that for $f(n)$ for all is odd all natural numbers ...
1
vote
1answer
66 views

Prove by inductive on the length of u

I have this question: Let u be a string, Prove by inductive on the length of u, that (u^R)^R = u "where R indicates reversal" I tried answer this question by this way: Basis step: u = 0 then ...
0
votes
1answer
223 views

Prove Complete Binary Tree using Induction

Recursive Definitions for Full Binary Tree The height of a full binary tree, written h(T), is dened recursively as follows. h(T) = 0 h(T1 T2) = 1 + max(h(T1); h(T2)) The number of nodes in a full ...
0
votes
1answer
57 views

Structural Induction Subsets

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3, 2) \in S$ (basis) • If $(x, y) \in S$, then $(3x − 2y, x) \in S$ ...
0
votes
3answers
124 views

Complex conjugate to the power proof

How can I proof using math induction that $$\overline{z^n} =\overline{z}^n$$ where $z$ is a complex number, $n$ is a positive whole number.
0
votes
2answers
148 views

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$.

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$. Prove your assertion. So my basis that I have is: Notice that (1)$^3$-(1)=0, and m(0)=0, so m ...
1
vote
2answers
45 views

Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

I have the following equation: $$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$ A little investigation: $T(2^1) = 1 + 2d$ $T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$ $T(2^3) = T(2^2) + ...
0
votes
1answer
63 views

Need help finding a proof strategy for a propositional logic theorem

Textbook is Ben-Ari's Mathematical Logic for Computer Science. This question is taken directly from the homework that my professor assigned, not from the textbook. Definitions of interpretations and ...
6
votes
1answer
93 views

A proof by strong induction that $a_n\le3^n$ where $a_n=a_{n-1}+a_{n-2}+a_{n-3}$

I am not sure whether this is right. Can anyone verify, whether this proof is valid? Thanks! Define a sequence $\{a_n\}_{n\ge0}$ as follows: ...
2
votes
2answers
68 views

On problems which can be proved easier if we use a different induction step.

Say we have a property $P$ defined on the natural nubers. Usually students are taught that to pove $P(n)$ is true for all $n\in\mathbb N$ you have to do the following: make a basis and use ...
3
votes
5answers
972 views

Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction: $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$ So far I have... Base case: Let n=1 and test $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$ ...
0
votes
3answers
60 views

Proof by Mathematical Induction?

Okay, I always get stuck proving things. I proved that it is true from the first value. I know that now I have to prove that it is true for $n+1$ to show that its true for any $n$. Below I wrote what ...
0
votes
1answer
23 views

Using strong/simple induction instead of structural induction.

Let S be the set of ordered pairs of integers defined recursively by $(0,0) \in S$ If $(a,b) \in S$, then both $(a+1, b+1) \in S$ and $(a+3,b) \in S$ And define the set $S'$ = {$(x,y) \in ...
0
votes
1answer
56 views

Prove this inequality by math induction

$$\sum \limits_{k=1}^{n-1} k^p < \frac{ n^{p+1}}{p+1} < \sum\limits_{k=1}^n k^p $$ I know how to prove it by using Riemann Sum, but it I was thinking if there is anyway to do it by mathematical ...
0
votes
3answers
75 views

Using mathematical induction?

Use mathematical induction to prove the following statement: For all $b\in\mathbb R$, and for all $n\in\mathbb N$, $$b>-1\implies (1+b)^n \geq 1+nb$$ When $n=1$, the inequality still holds $1+b ...
1
vote
2answers
56 views

conjecture and prove sequence value using induction

Conjecture and prove $a_n$ for $n\ge 0$. $a_n=\sum_{i=0}^{n-1}{{n-1}\choose {i}}a_ia_{(n-1)-i},n\ge 1; a_0 $ a fixed constant.
1
vote
1answer
34 views

Recurrence Algorithms

What is the best method of solving non standard recurrence algorithms? In particular something like the following: What would be it's tight bound in Theta notation? $$ n \in N\\ T(n) = \sqrt{n} \; ...