Tagged Questions

21 views

conjecture formula/prove by induction

Conjecture formula from following equations, and prove conjecture: $1=1,\\2+3+4=1+8,\\5+6+7+8+9=8+27,\\10+11+12+13+14+15+16=27+64\\$ $S(n)=\sum_{i=(n-1)^2+1}^{n^2}i=(n-1)^3+n^3$ ...
65 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
42 views

Prove or Disprove n! = BigOh(2^n) via mathematical induction.

My computer science professor has us tasked with proving or disproving the statement the n! = BigOh(2^n). We are then suppose to say if it's always true, always false, or non-conclusive, ...
54 views

Prove this by induction?

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: So obviously, the ...
40 views

prove that the sum to n terms of the sequence is $n(n+1)/2(2n+1)$ [duplicate]

Prove that the sum to n terms of the Sequence: $1^2/(1×3),2^2/(3×5),3^2/(5×7),...$ is $n(n+1)/2(2n+1).$ Im having trouble with this question, firstly ive begun by stating that p(n) denotes the ...
45 views

Strong mathematical induction with a sequence

The question: The terms of a sequence are given recursively as $a_0 = 1$, $a_1 = 1$ and $a_n=2a_{n-1} + 3a_{n-2}$ for $n \geq 2$ prove by mathematical induction $a_n = \frac12(3^n) +\frac12(-1)^n$ ...
30 views

Induction assuming n-1

In induction, I always thought that one assumed that some statement was true for n and then showed it's true for $n+1$. But in one proof I am trying to understand, I think that they assume that it's ...
21 views

What is the intuition behind the solution to the “Surveyevor” problem?

I was looking at the "Surveyevor" problem in the MIT OCW site: here. This is more or less what it says: In a new reality TV series called Surveyevor, a group of contestants is placed on a small ...
56 views

Prove by induction: $1(1!)+\cdots + n\cdot n!$ = (n+1)! - 1

Induction step. $1(1!) + ... + n(n!) = (n+1)! - 1$ $1(1!) + ... + n(n!) + (n+1)(n+1)! = (n+1)! - 1 + (n+1)(n+1)!$ So, I don't understand how to get $(n+2)! - 1$ from $(n+1)! - 1 + (n+1)(n+1)!$. ...
123 views

Show that $n^3+2n$ is divisible by 3 for all $n\ge 1$

i want to prove it with mathematical induction : first i am tried with n=0 then it is divisible by zero then i move to next step change all n with K then i get this product : $$P(K)=K^3+2K = 3m$$ ...
31 views

Proof an inequality by mathematical induction

I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is: Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\$ So, I did that ...
50 views

Finishing Induction Step

I am currently writing a proof for the following problem $$\sum\limits_{i=1}^n i^22^i = n^22^{n+1}-n2^{n+2}+3*2^{n+1}-6$$ By induction on $n\ge0$ My question isn't really about how to correctly ...
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
67 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
63 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).